4 ms·
Symbolic Execution: Intuition and Implementation
- sklivvz1971 9y ago> The rationale, of course, is to feed in values that test each code path That's the absolutely wrong way to test a function. You want to test a function so _as the implementation changes, the same output follows the same inputs_. Counterexample: I might refactor that function without those code paths (e.g. write `x*sign(x)` instead). Do I need only one test now? Morale: DO NOT TEST IMPLEMENTATIONS
- ghettoimp 9y agoIf none of your test cases ever hit some lines of your functions, it seems pretty clear that your tests are missing functionality. Of course, hitting each line with a single test doesn’t guarantee your tests are “sufficient,” but pragmatically it seems like a reasonably good and easy to understand starting point.
- dang 9y agoCould you please not use uppercase for emphasis in HN comments? This is in the site guidelines: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html.
- taeric 9y agoI think you are viewing it not as an iterative process. If you have code that isn't covered by a test, then by all means feel free to refactor such that that code isn't needed. If you can look at it and see the code is needed, then you are clearly lacking a test that shows why it is needed. You can let both ends inform the next step.
- adrianratnapala 9y agoThe (rhertorical) question the author was asking is how would a machine back out a reasonable set of test cases from the source code. The fact that this code branches conditionally on the sign of the input is a hint that the test set should worry about sign. Tests derived this way will still be useful if the implementation were changed to something that didn't branch. I suspect though that we shouldn't get too stuck on the testing thing. The author only asked the question to introduce thinking about how to abstract expectations behviour out of concrete code. Test generation is only one of the uses he cites.
- thechao 9y agoSo... abstract interpretation?
- arnarbi 9y agoYes. Symbolic execution is an example of abstract interpretation. Not sure why the snark, that's fairly accepted terminology.
- jes 9y agoMany years ago, I lead a small team of very talented software developers. We built "execution trace disassemblers" 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. 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., "Was the instruction data in this i-fetch data cycle executed by the processor?") and then, if the assumption seems solid, reasoning about how the state of the processor (e.g., the general registers) must have changed. 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. It was a very cool piece of software for its time, which was the late 1980s / 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.
- seattleeng 9y agoIt's been a while since I've dealt with computer architecture -- what is an "in-circuit emulator"? Did this mean that having access to just the data bus (typically exposed outside of the CPU die to external memory) meant that you could infer what was on the instruction bus?
- tzs 9y agoClassically, an ICE was a development/debugging tool sold by processor manufacturers. An ICE for a particular processor included a special version of that processor that had many more pins than normal. These pins brought out various internal buses and signals for inspection and control. There would be a ribbon cable with a plug compatible with the normal socket for that processor model. You'd take out your regular processor, and plug the ICE into the socket. The ICE would have a normal processor that used the extra signals on the special processor to control it, and to provide a user interface that would let the user control all kinds of aspects of the special processor's execution that normally are invisible. Here's a nice table comparing ICEs with other tools used to debug embedded systems: www.ganssle.com/articles/ice.htm In the '70s and '80s (and probably beyond) an ICE was an invaluable tool for embedded developers. Actually, it was pretty damned useful to any low level developer, not just embedded developers. I had a job once where I was rewriting the whole memory and process subsystems on a port of a swapping Unix to turn it into a demand paged system, running on a 68020. There were some subtle bugs in the interaction between page fault handling and signals that I had not considered [1] and an ICE made figuring them out a lot nicer. Without an ICE back in those days, even a simple task as figuring out what is overwriting something in memory that should not be getting overwritten could be complicated. Maybe if you had a logic analyzer with enough channels and enough history you could trigger on seeing writes to that memory on the bus, and go far enough back in history to figure out from the instruction fetch bus cycles what code was doing it. But with an ICE you could simply set a trigger to pause when the processor tries to write the monitored location, and then examine the program counter directly. You don't have to be anywhere near embedded or OS development to have a "who the hell is overwriting this?!" problem. Nowadays, processors often include built-in debugging features that in many cases eliminate the need for an ICE. For example, the 386 had 4 debug registers that could be loaded with addresses, and configured to trigger breakpoints if those addresses were accessed. The breaks could be configured to be on execution, break on write, or break on read/write, and could be configured to cover 1, 2, or 4 bytes starting at that address. That gives you a good chance to reasonably efficiently track down those overwriting bugs without an ICE. I haven't looked at low level debugging in a while, but I'd expect that processors nowadays go far beyond the 386's debug register capabilities, allowing much more to be done without ICE than we could back in the day. Also, I believe many smaller processors nowadays include interfaces that expose some of the information and control functions that the special ICE processors exposed. They expose this over a serial interface that only takes a handful of pins, and this is included standard in the processors. So no more need to replace the processor with a special one...you just need to design your system so those pins are accessible. I don't think you can do everything an ICE could do with this kind of processor interface (at least not in real time like you could with an ICE) but most of the time it should be good enough. [1] There are a couple ways a processor can deal with an instruction that gets interrupted in the middle. One way, which is what I believe Intel uses, is "instruction restart". The interrupt discards any partially completed work of the instruction, and when you resume from the interrupt it starts the instruction over. Another way, which is what Motorola used in the 68020, is called "instruction continuation". The interrupt saves any partially completely work on the stack, and when you resume after the interrupt it picks up where it left off. So suppose the 68020 is cruising along in user mode, and the code generates a page fault. That interrupts the instruction, and the processor pushes a stack frame that contains a bunch of internal processor state. The page fault handler arranges to get the page loaded and mapped, and does a return from interrupt, and everyone is happy. That's the normal case. But imagine that while the page fault is being processed, the annoying bastard user hits ^C, and that irritating git has got a SIGINT handler. The kernel, when it gets ready to return to the user after the page fault notices that it has a signal that needs delivery to a user signal handler. So it alters the return address in the interrupt stack frame to point to the SIGINT handler instead of the page faulting instruction, and diddles the stack so that when the SIGINT handler returns, it will return to the page faulting instruction. On an instruction restart processor, that would be fine. On an instruction continuation machine, that return from the interrupt to the SIGINT handler loads internal state from halfway through the interrupted instruction, and then tries to use it to continue a different instruction from the middle. Who knows what havoc that will cause? And then, if that didn't crash it, when the SIGINT handler returns the page faulting instruction will start from the beginning. If it had been an instruction with side effects (say, incrementing an address register) and those side effects happened before the page fault...they will happen again. From my point of view, all I was seeing was if I had the system under enough memory load that I was getting a lot of page faults, hitting ^C would sometimes just totally lock things up. An ICE let me get a look at what the heck was actually going on, and realize my mistake. (The fix? I made it so that if the kernel was returning from a page fault interrupt and there was a signal that needed delivery to a user signal handler in that process, it would alter the saved flags in the interrupt stack frame to turn on the single step debug flag, and would not diddle anything else on the stack. That lets it return from interrupt, the page faulting instruction resumes from where it left off, completes, and then the single step interrupt goes off, getting us back to the kernel. The kernel can then clear the single step flag, and go through the normal interrupt code, which sees the pending signal and does the usual stack frame molesting to deliver it, which is safe because it knows the single step interrupt is a simple interrupt that does not save internal processor state). (Instruction continuation is also a pain on multiple CPU systems, although we were only making a single CPU system so did not have to deal with that aspect. Since page faults save internal processor state, and since what exactly is saved can vary from revision to revision of the CPU, you have to be careful to make sure that when you resume a process after a page fault, you resume on the same processor that took the fault, or at least on one that is the exact same revision. You want to resume on the same CPU if you can anyway, because that will generally be better because of on-chip caches...but all you risk there if you don't is worse performance. If you resume after a page fault on the wrong CPU you risk locking up the system).
- dguido 9y agoCheck out DeepState, a Google Test-like library for easily using symbolic execution in C/C++ apps. It's still very early on but it's already usable! https://github.com/trailofbits/deepstate https://github.com/trailofbits/deepstate
- alpb 9y agoThis is posted before: https://news.ycombinator.com/item?id=16532053 https://news.ycombinator.com/item?id=16532053 Please refrain from posting your own site, especially multiple times. :)
- jwilk 9y agoNo, it's OK to post your own site. HN FAQ says: If a story has had significant attention in the last year or so, we kill reposts as duplicates. If not, a small number of reposts is ok. The linked post had no comments, so it clearly doesn't qualify as having "significant attention".
- fulafel 9y agoFor those wondering about applicability of SE to other languages, see here for a compendium of tools: https://github.com/ksluckow/awesome-symbolic-execution https://github.com/ksluckow/awesome-symbolic-execution
- leipavoi 9y agoI think symbolic execution is quite an "academic subject". Things could change as I think symbolic execution would very well fit when analyzing and verifying the correctness of smart contracts in blockchain.
- Patient0 9y agoTo me there's a lot of similarities between this and type inference. "First, as we step through this program, we don’t think about specific values of x like 13. Instead, we think about the set of possible values x might take on. At different points in the program, x might be an element of all integers, negative integers, or positive integers plus 0. In other words, we think of x as a symbolic value (i.e., a set of possible values) rather than a concrete value (i.e., a particular element of that set of possible values)." vs: "We expound a view of type checking as evaluation with ‘abstract values’." http://okmij.org/ftp/Computation/FLOLAC/lecture.pdf http://okmij.org/ftp/Computation/FLOLAC/lecture.pdf
- int3 9y agoType inference is a special case of abstract interpretation: https://www.irif.fr/~mellies/mpri/mpri-ens/articles/cousot-types-as-abstract-interpretations.pdf https://www.irif.fr/~mellies/mpri/mpri-ens/articles/cousot-t... (Not that I've read that paper in detail, mind you...)
- UncleMeat 9y ago"Abstract values" and "symbolic values" mean different things. Abstract interpretation and symbolic execution are both powerful static analysis techniques, but they are not (classically) equivalent in function.
- fenollp 9y agoFunny Klee [1] wasn't mentioned. [1]: https://github.com/klee/klee https://github.com/klee/klee
- nickpsecurity 9y agoI recommend people look through their whole publication list here: http://klee.github.io/publications/ http://klee.github.io/publications/ That group does some amazing work bridging neat theories and putting things into practice. I wish more researchers would build on KLEE to see just how much more it could accomplish. That is, on top of more developers using tools like it.
- touisteur 9y agoOr cbmc (some interesting papers : http://www.cprover.org/cbmc/applications/ http://www.cprover.org/cbmc/applications/), they're on GitHub : https://github.com/diffblue/cbmc https://github.com/diffblue/cbmc), seems to also handle java, not sure... Or angr (http://angr.io http://angr.io) which works on binaries and is in python and is loads of fun to use... On small codebases ? Still some people have used it in combination with AFL to help the fuzzer when it's stuck ('driller' : https://github.com/shellphish/driller https://github.com/shellphish/driller) Or manticore (you'll need IDA Pro there ?) : https://blog.trailofbits.com/2017/04/27/manticore-symbolic-execution-for-humans/ https://blog.trailofbits.com/2017/04/27/manticore-symbolic-e... There's a good survey there : https://arxiv.org/abs/1610.00502 https://arxiv.org/abs/1610.00502 (no cbmc though). But nickpsecurity is right, Klee seems to be the place where most of the interesting stuff seems to be happening right now. The recent improvements in SMT/SAT solvers bring back lots of techs that were thought impractical (formal proof, symbolic execution...) a while back.
- Chris2048 9y agoI actually started building something similar in Python: it uses Mockito like 'mock"/"spy" objects to record calls to its methods, and the idea was to eventually branch at every test condition to automatically derive possible execution paths. Might go back to that :-) The trick would be that conditions are tested via magic methods that return True/False (e.g. for > or ==), so you just need to branch at every test. You don't even need specific test values, just substitute object e.g if the test is X > Y, you don't need actual numbers, just an X that returns True/False for __gt__, and any Y since the actual evaluation is X.__gt__(Y). If more nuance is needed (consistency so that X > Y always has the same answer... unless you want to test for exotic things like inconstant 'number' objects) then you can have X return True/False depending on if passed argument 'is' the Y object. Maybe embed Y in X or a shared data-struct so that it can make this identification.