moralismercatus
commented
9 years ago I notice that a direct comparison is not possible. The reason is that across different iterations, the addresses may be different. At least addresses will need to be ignored in the comparison.
Example: In tb-4, on iteration 0: ret i64 139736910016880 In tb-4 on iteration 3: ret i64 139736913404240
But otherwise the TBs and main() are identicle. I ignore ret instructions and alloca (added for some reason to the beginning of TBs, but unused).
The function names for tbs shouldn't differ, as these are determined at compile time and accessible via ELF.
Problem: A given test case may generate an execution trace that, while likely not identical to a previous, will result in a redundant set of test cases being generated after symbolic execution.
That is, the paths covered have already been covered, and therefore the any new tests that result in the same paths being taken will be redundant. This issue a significant time overhead.
Solution: Note: we need more thought as to whether this approach actually discards only redundancies, and if it discards some non-redundancies, if it's acceptable (as we've already committed ourselves to not proving program correctness by using concolic testing).
A, perhaps naive, initial approach will be parse the execution trace dumped from the VM. Two aspects will be used to determine execution trace uniqueness. First, the order and number of translation blocks executed. Second, the translation blocks themselves. If both of these aspects are identical, then we assume the execution trace is redundant and discard it. To make comparisons between iterations efficient, I will create hashes for each execution trace based on those two aspects.
If we can discard the execution trace before it is even executed by the SE, we will greatly improve performance.