LLPE -7 Gives Assertion Errors

[aatiranum]

I want to use LLPE on my own set of examples such as mini_httpd, gzip, binutils etc.
I have downloaded and installed LLPE -7 version from github but it gives errors on these.

Can you help me suggest which version of LLPE is most update and complete so that I can use those?
Secondly, I am using the following command to invoke LLPE.

opt -load /home/aatiranum/llpe/build/main/libLLVMLLPEMain.so -load /home/aatiranum/llpe/build/driver/libLLVMLLPEDriver.so -mem2reg -simplifycfg -loop-simplify -lcssa -llpe -spec-argv 0,1,tmp/argv unspecialized.bc -o specialised.bc

Am I doing fine?

I am also attaching some of the screen shots of examples I found errors with. The bitocde files are made by wllvm and currently I am not building with C library.

Please help me out solving these errors.
examples.zip

[smowton]

I have a working branch at https://github.com/smowton/llpe/tree/experimental/llvm-7-fixes which fixes the problems I noticed with Aircrack and Airtun -- both of these now complete without error (they may or may not be sound, of course!)

Bzip2 says "Warning: block in BZ2_decompress has predecessor that comes after it topologically, but this is not a loop header. The program is not in well-nested natural loop form." -- there's a function not in simple loop form (given its purpose, probably a state machine built from GOTOs). This would need transforming first -- for example, by turning a function:

void f() {
  a: ... goto b;
  b: ... goto a;
  c: ... goto c;

with something like

void f() {
  int nextBlock = 0;
  do {
    switch(nextBlock) {
      case 0:
         ... nextBlock = 1; break;
      case 1:
         ... nextBlock = 0; break;
      case 2:
         ... nextBlock = 2; break;
    }
  } while(1)
}

Generally it's necessary to add extra state to track the control-flow to massage the thing into natural loop style. There might even be an automated LLVM pass out there to do this, though last time I checked there wasn't.

I'll take a look at the other projects gzip mini_httpd netperf totd wget later this week.

[aatiranum]

I got this error in aircrack-ng when returning from LLPE GUI.
PHINode should have one entry for each predecessor of its parent basic block!
%3808 = phi i32 [ 2, %5545 ], [ 2, %3946 ], [ 0, %5543 ], [ 1, %5547 ]
LLVM ERROR: Broken function found, compilation aborted!

[aatiranum]

bzip2 still gives the same assertion error. Is it due to what you mentioned above or by changing the code it will remove?

[aatiranum]

when I link airtun-ng with libc.a.bc (got from github/musl-llvm) using llvm-link and then run llpe, it gives following error,
.....opt: /usr/local/include/llvm/ADT/IntervalMap.h:630: unsigned int llvm::IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits>::insertFrom(unsigned int&, unsigned int, KeyT, KeyT, ValT) [with KeyT = long unsigned int; ValT = bool; unsigned int N = 11u; Traits = llvm::HalfOpenWithMerge]: Assertion `!Traits::stopLess(b, a) && "Invalid interval"' failed.

[smowton]

bzip2 still gives the same assertion error. Is it due to what you mentioned above or by changing the code it will remove?

Yes, bzip2 would need some manual translation as described above.

[smowton]

I've pushed further fixes to that branch -- all your example programs except bzip2 now run for at least a few minutes (the limits of my patience for this testing :)) without crashing, both with and without musl-libc linked.

I noticed netperf + libc crashed due to not being in well-nested loop form in musl's function mbsrtowcs -- sounds like a unicode codec -- which would require similar therapy to the bzip2 function featuring interesting control-flow, likely a state machine built from gotos.

Finally, given all these examples produce lots of clobber-all warnings (essentially, a write through a pointer whose target is unknown, causing more or less all known data to be thrown away), which suggests the specialisation results will be poor. Back when I was last doing this seriously (2014), my usual strategy was to pare down the example programs and use the GUI to inspect why we had a write through a pointer that could point anywhere. In this way we can incrementally tweak either the specialisation settings or the target program to get a good result.

[aatiranum]

Thank you so much. I will check and let you know next week about it. There are few other examples as well that I need to run on LLPE-7. Right now I need you to comment on my understanding on LLPE. I need to confirm few things.

1. Reading from the paper in the repo and your thesis, LLPE evaluates each LLVM instruction, calculating its result if its arguments are known or marking it to be residualized otherwise. Instructions are in effect symbolically executed over a domain consisting of constants, symbolic pointers (allocation and offset pairs), symbolic file descriptors used to model system call interactions, and a special “residualize” value. Is is right?
2. Secondly it only supports open,read, lseek, close instructions but not fopen, fread, fseek fclose?
3. Thirdly, i need to know that in your evaluation of nigix and mongoose, did your root function was main or it was any other function?
4. Fourthly, what LLPE does if a function has multiple callsites? Did you inline each and every callsite or is your tool context-insensitive i.e. only inline functions with 1 callsite?
5. Does the examples which were not working on LLPE such as bzip2 implies that LLPE require changes to code which has a backward goto statement that is loop must be in natural form?