Avalanche-0.4 finished of checking an application but did't find an actual bug

[GoogleCodeExporter]

Test environment:
x86
Ubuntu 10.04 32 bit (2.6.32-33-generic i686 SMP) in Virtualbox OSE 4.0.4, 2 
core of i5-2500, 768 mb of RAM
Host OS: ubuntu 11.04 64 bit (2.6.38-10-generic x86_64 SMP)
compiler: gcc version 4.4.3

Tested application:
3. p7ip-9.04  (Real bug: 
http://sourceforge.net/tracker/?func=detail&aid=2863580&group_id=111810&atid=660
493)
confirm: ~/workspace/p7zip_9.04$ ./bin/7z x 
~/Downloads/1e1a4fcdfe3092387458167488d4fdb2.rar 
7-Zip 9.04 beta  Copyright (c) 1999-2009 Igor Pavlov  2009-05-30
p7zip Version 9.04 (locale=en_US.utf8,Utf16=on,HugeFiles=on,4 CPUs)
Processing archive: /home/ioex/Downloads/1e1a4fcdfe3092387458167488d4fdb2.rar
Segmentation fault (core dumped)

in.rar is a valid archive:
~/workspace/p7zip_9.04/avtest$ ./bin/7z x ./in.rar 

7-Zip 9.04 beta  Copyright (c) 1999-2009 Igor Pavlov  2009-05-30
p7zip Version 9.04 (locale=en_US.utf8,Utf16=on,HugeFiles=on,4 CPUs)

Processing archive: ./in.rar

Extracting  in

Everything is Ok

Size:       236
Compressed: 280

avalanche cmd line: ~/avalanche-0.4/bin/avalanche --filename=./in.rar ./bin/7z 
x ./in.rar

Status: completed
Time consumed: ~ 7 days
Results: 10345 exploits

Verify perl script:
my $i=0;
while($i<10345)
{
    system("./bin/7z x ./exploit_${i}_0");
    $i++;
}
cmd line: perl p.pl 2>&1 > verify2.log; 
verify2.log additionally was sorted by unique strings

It seems, the avalanche premature finished of checking the application 

Original issue reported on code.google.com by xeioexception on 1 Sep 2011 at 6:27

Attachments:

• 1e1a4fcdfe3092387458167488d4fdb2.rar
• p7zip_9.04_src_all.tar.bz2
• in.rar

[GoogleCodeExporter]

Unfortunately, we cannot guarantee that all existing defects in the application 
will be detected by Avalanche. The main reason for this is that Avalanche 
traces only explicit tainted data flow (further explanation can be found in 
articles present in Downloads section).

verify2.log seems to suggest that all detected exploits do not lead to 7z 
crashing. Is this the case?

Original comment by m.k.erma...@gmail.com on 2 Sep 2011 at 1:44

[GoogleCodeExporter]

Sorted verify2.log was added.

Yes, all detected exploits do not lead to 7z crashing

Original comment by xeioexception on 2 Sep 2011 at 1:53

Attachments:

• verify2.log

[GoogleCodeExporter]

Could you please upload several exploits and approximate time of detection, if 
this is possible?

Thanks in advance!

Original comment by m.k.erma...@gmail.com on 2 Sep 2011 at 4:13

[GoogleCodeExporter]

>Could you please upload several exploits and approximate time of detection, if 
this is possible?
Sure, I attached several exploits.
First approximate detection time is about ~ 4 days.

Original comment by xeioexception on 5 Sep 2011 at 5:32

Attachments:

• exploits.tar.gz

[GoogleCodeExporter]

I can't reproduce the problem. Been running Avalanche for over a week; no 
exploits detected and the amount of new inputs to check is in the 400000s and 
is still increasing - not likely it will stop.

Original comment by m.k.erma...@gmail.com on 12 Sep 2011 at 8:55

[GoogleCodeExporter]

What environment did you use for this checking? May be the issue is related to 
it.

Original comment by xeioexception on 12 Sep 2011 at 9:37

[GoogleCodeExporter]

It seems I have missed the fact that your machine is faster than the one I was 
using - probably enough to explain no exploits. I had to stop my run due to the 
size of log file - I'll configure logging options and check again.

Original comment by m.k.erma...@gmail.com on 12 Sep 2011 at 4:25

[GoogleCodeExporter]

My guess, limited RAM size is the most possible reason.

Original comment by xeioexception on 13 Sep 2011 at 1:52

[GoogleCodeExporter]

In the matter of explicit tainted data flow.
Lets simplify the task for the tool by using function filtering:

Environment: The same

1) ~/avalanche-0.4/bin/avalanche --dump-calls --verbose --filename=./in2.rar 
./bin/7z -y x ./in2.rar

2) cat funcsname 
NCompress::NRar3::CDecoder::DecodeLZ(bool&)

in2.rar normal rar archive truncated to 181 byte as real bad archive is
3)ioex@ioex-desktop:~/workspace/p7zip_9.04/avtest$ 
~/avalanche-0.4/bin/avalanche --func-file=funcsname --filename=./in2.rar 
../bin/7z -y x ./in2.rar 
Starting iteration 0
Starting iteration 1
Starting iteration 2
Starting iteration 3
Starting iteration 4
Starting iteration 5
Starting iteration 6
Starting iteration 7
Starting iteration 8
Starting iteration 9
Starting iteration 10
Starting iteration 11
Starting iteration 12
Starting iteration 13
Starting iteration 14
Starting iteration 15
Starting iteration 16
Starting iteration 17
Starting iteration 18
Starting iteration 19
Starting iteration 20
Starting iteration 21
Starting iteration 22
Starting iteration 23
Starting iteration 24
Starting iteration 25
Starting iteration 26
Starting iteration 27
Starting iteration 28
Starting iteration 29
Starting iteration 30
Starting iteration 31
Starting iteration 32
Starting iteration 33
Starting iteration 34
Starting iteration 35
Starting iteration 36
Starting iteration 37
Starting iteration 38
Starting iteration 39

Exploits report:

Why do avalanche could't find bug again?

Thanks in advance!

Original comment by xeioexception on 13 Sep 2011 at 2:27

Attachments:

• calldump.log
• in2.rar

[GoogleCodeExporter]

Function filtering quite often doesn't not produce good results. Here's the 
example:

int k;

int foo (char x)
{
  if (x == '3') k = 1;
}

int main(int argc, char** argv)
{
  int  j = 0;
  char local[3];
  int  fd1 = open(argv[1], O_RDONLY | O_CREAT, S_IRWXU);

  read(fd1, local, 3);
  foo(local[0]);
  if (local[1] == '3' && k == 1) {
      abort();
  }
  return 0;
}

Unless we satisfy the first condition (local[0] == '3') in foo(), we can't 
satisfy the second one.

Now, running Avalanche like this:
./inst/bin/avalanche --func-name=main --suppress-subcalls 
--filename=samples/simple/seed ./test samples/simple/seed
will not get the exploit (suppress subcalls will cut out foo()).

Original comment by m.k.erma...@gmail.com on 14 Sep 2011 at 10:02

Attachments:

• test.c

[GoogleCodeExporter]

Could you clarify which branches are covered in case of one simple filtered 
function without --suppress-subcalls option enabled.

I have prepared two illustration. Which is most suitable one? Or may be 
something completely different, please clarify. 

My guess by source code avalanche implements only ordinary function filtering, 
isn't it?

Thanks in advance!

But it seems, the most proper way is a smth. like full function prehistory 
branching.

Original comment by xeioexception on 14 Sep 2011 at 1:43

Attachments:

• full-prehistory-branching.odg
• ordinary-filtered-func-branching.odg

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

If we specify filtering one function without suppress-subcalls, we will check 
only branches that split between the entry point to this function and the 
return point from it. This means that branching in nested calls will be 
registered too. And --suppress-subcalls adds filtering for nested calls.

Yes, Avalanche performs only ordinary function filtering; the logic behind this 
implementation is the following:
Consider an application working with files with headers and raw data (the 
majority of our "test subjects"). If it has a function that (with its nested 
calls) performs raw data processing, ordinary function filtering is the desired 
approach, because we do not want to waste resources on header processing. This, 
of course, can be done with input file filtering using masks. However, 
combining these two approaches can be even more efficient.

I must admit that prehistory branching does indeed seems like more proper 
approach (the less information we lose, the better), but we wanted exactly to 
narrow the analysis to the scope of subject function.

Thanks again for your interest!

Original comment by m.k.erma...@gmail.com on 14 Sep 2011 at 3:32

[GoogleCodeExporter]

Original comment by m.k.erma...@gmail.com on 2 Nov 2011 at 9:30

• Changed state: WontFix