Discussions on the data structures and algorithms

[thuanpv]

Hi @alan32liu ,

Following is the pseudo code of the current algorithm and how we could make changes to integrate MCTS

MCTS-Initialisation

function main

while (not timeout) //main loop
Begin
//MCTS-Selection ~ choose_target_state + choose_seed
s = choose_target_state() ⇒ select_tree_node
t = choose_seed(s) //t is a sequence of messages ⇒ select_seed
fuzz_one(t) //generates N more sequences
end

function fuzz_one

N = calculate_score(t) //energy for the test t
count = 0
while (count++ < N) //generate N new tests/new sequences from t
begin
t’ = mutate(t) //the logic is in fuzz_one
common_fuzz_stuff(t’) //run the server, send t’ to the server and
//observe the server’s behaviours
end

function common_fuzz_stuff(t’) ~ MCTS-Simulation() -- the logic is already implemented in AFLNet

(is_interesting, response_codes) = run_target(t’) //send messages
if (is_interesting) update_state_aware_variables(t) => MCTS-Expansion

[thuanpv]

Regarding the tree, I have run the LightFTP subject and get the following 3 sequences of responses codes
0-220-331-230-215-257-200-150-451-221 (ftp_requests_full_anonymous)
0-220-331-230-215-257-200-150-451-257-221 (ftp_requests_full_normal)
0-220-500-500-215-530-215-530-530-221 (another_test)

Can you please manually draw a tree, based on your current data structure, using the above traces? Thanks.