Symbolic Execution: Intuition and Implementation
Many years ago, I lead a small team of very talented software developers. We built &quot;execution trace disassemblers&quot; for in-circuit emulators. Basically, they took an array of bus cycles recorded from the bus of a microprocessor based system, and re-created the instruction stream (expressed as assembly language instructions) that must have been executed to result in the given set of bus cycles.<p>It was an interesting problem to solve. Generally speaking, it was a search problem, constantly looking for evidence to confirm or contradict an assumption being made about some bus cycle (e.g., &quot;Was the instruction data in this i-fetch data cycle executed by the processor?&quot;) and then, if the assumption seems solid, reasoning about how the state of the processor (e.g., the general registers) must have changed.<p>Once it got started disassembling a trace, it learned the contents of the general registers, and we were able to annotate the reconstructed assembly language listing, to show the actual data that was operated on.<p>It was a very cool piece of software for its time, which was the late 1980s &#x2F; early 1990s. Eventually, though, microprocessors got internal caches, which made the problem much harder. Some microprocessor vendors though, provided undocumented features that allowed us to snoop what was happening on-chip.