When should we update the tree?

[thuanpv]

I think it is quite important to know when we should update the tree. Suppose that the Selection function selects a node n on the tree and a seed s (of type struct queue_entry*) for simulation (i.e., mutate(s) and run(s)), we could consider 3 points in time at which we should update the tree. Note that mutate(s) should generated N new tests/seeds where N is mainly decided by the calculate_score function. This is related to the energy concept we introduced in the AFLFast CCS'16 paper.

1) After every single test 2) Once all tests have been executed 3) After every "interesting" test that increases the coverage, for example.

So based on MCTS, when should we update the tree?

[DonggeLiu]

In Legion, we update the tree in two ways: a) Update the statistical values in the tree (as in propagation); b) Add in new traces (as in expansion). In this setting, 1&2 seem to be the same, as we will record all tests before the next selection step. I reckon 3 will ignore the boring tests? In that case, we will need to be careful about the fairness of a), as some nodes might seem to be interesting because we have ignored the boring tests of it. For b), that should not matter too much, as long as we record all new traces.

Vanilla MCTS only has a), I think Legion's algorithm is more suitable to our situation, though.