thesis/3_rasta/4_failures_analysis.typ

#import "../lib.typ": todo
#import "../lib.typ": paragraph
#import "X_var.typ": *
#import "X_lib.typ": *

== Failure Analysis <sec:rasta-failure-analysis>

In this section, we investigate the reasons behind the high ratio of failures presented in @sec:rasta-xp. 
@tab:rasta-avgerror reports the average number of errors, the average time and memory consumption of the analysis of one APK file. 

#figure({
  show table: set text(size: 0.50em)
  show table.cell.where(y: 0): it => if it.x == 0 { it } else { rotate(-90deg, reflow: true, it) }
  show table.cell.where(x: 0): it => text(size: 1.2em, it)
  show "sigma": $sigma$
  let time_num(n) = num(calc.round(float(n), digits: 0))
  table(
    columns: (auto, auto, ..for i in range(20) { (1fr,) }),
    //inset: (x: 0% + 5pt, y: 0% + 2pt),
    stroke: none,
    align: center+horizon,
    table.header(
      [*Exit status*], [], 
      [adagio], [amandroid], [anadroid], [androguard], 
      [androguard_dad], [apparecium], [blueseal], [dialdroid], 
      [didfail], [droidsafe], [flowdroid], [gator], [ic3], 
      [ic3_fork], [iccta], [mallodroid], [perfchecker], 
      [redexer], [saaf], [wognsen_et_al],
    ),
    ..for i in range(2, 22) {
      (table.vline(x: i, end: 3),
      table.vline(x: i, start: 4))
    },

    table.cell(colspan: 22, inset: 3pt)[],
    table.hline(),
    table.cell(colspan: 22)[*Average number of errors (and standard deviation)*],
    table.hline(),
    table.cell(colspan: 22, inset: 3pt)[],
    
    ..rasta_avg_nb_error_by_exec
    .map(e => {
      let row = ([#e.type], 
        num(e.adagio), num(e.amandroid), num(e.anadroid), num(e.androguard), 
        num(e.androguarddad), num(e.apparecium), num(e.blueseal), num(e.dialdroid),
        num(e.didfail), num(e.droidsafe), num(e.flowdroid), num(e.gator), num(e.ic),
        num(e.icfork), num(e.iccta), num(e.mallodroid), num(e.perfchecker), 
        num(e.redexer), num(e.saaf), num(e.wognsenetal)
      )
      if e.first != "" { row.insert(0, table.cell(rowspan:2)[*#e.first*]) }
      row
    }).flatten(),

    table.cell(colspan: 22, inset: 3pt)[],
    table.hline(),
    table.cell(colspan: 22)[*Average time (s)*],
    table.hline(),
    table.cell(colspan: 22, inset: 3pt)[],
    
    ..rasta_avg_time
    .map(e => {
      let row = ([*#e.first*], 
        time_num(e.adagio), time_num(e.amandroid), time_num(e.anadroid), time_num(e.androguard), 
        time_num(e.androguarddad), time_num(e.apparecium), time_num(e.blueseal), time_num(e.dialdroid),
        time_num(e.didfail), time_num(e.droidsafe), time_num(e.flowdroid), time_num(e.gator), time_num(e.ic),
        time_num(e.icfork), time_num(e.iccta), time_num(e.mallodroid), time_num(e.perfchecker), 
        time_num(e.redexer), time_num(e.saaf), time_num(e.wognsenetal)
      )
      if e.type != "" { row.insert(1, table.cell(rowspan:3)[*#e.type*]) }
      row
    }).flatten(),

    table.cell(colspan: 22, inset: 3pt)[],
    table.hline(),
    table.cell(colspan: 22)[*Average Memory (GB)*],
    table.hline(),
    table.cell(colspan: 22, inset: 3pt)[],
    
    ..rasta_avg_mem
    .map(e => {
      let row = ([*#e.first*], 
        num(e.adagio), num(e.amandroid), num(e.anadroid), num(e.androguard), 
        num(e.androguarddad), num(e.apparecium), num(e.blueseal), num(e.dialdroid),
        num(e.didfail), num(e.droidsafe), num(e.flowdroid), num(e.gator), num(e.ic),
        num(e.icfork), num(e.iccta), num(e.mallodroid), num(e.perfchecker), 
        num(e.redexer), num(e.saaf), num(e.wognsenetal)
      )
      if e.type != "" { row.insert(1, table.cell(rowspan:3)[*#e.type*]) }
      row
    }).flatten(),

    table.cell(colspan: 22, inset: 3pt)[],
    table.hline(),
  )
  [
  ]},
  caption: [Average number of errors, analysis time, memory per unitary analysis -- compared by exit status],
) <tab:rasta-avgerror>


 
=== Error Detected //<sec:rasta-errors>

/*
capture erreurs
fichiers
stdout, stderr
(only 4%) 
android.jar en version 9 qui génère des erreurs
*/

During the running of our experiments we parse the standard output and error to capture:

- Java errors and stack traces
- Python errors and stack traces
- Ruby errors and stack traces
- Log4j messages with a "ERROR" or "FATAL" level
- XSB error messages
- Ocaml errors

For example, Dialdroid reports in average #num(55.9) errors for one successful analysis. 
On the contrary, some tools such as Blueseal report very few error at a time, making it easier to identify the cause of the failure. 

Because some tools send back a high number of errors in our logs (up to #num(46698) for one execution), we tried to determine the error that is linked to the failed status. 
Unfortunately, our manual investigations confirmed that the last error of a log output is not always the one that should be attributed to the global failure of the analysis. 
The error that seems to generate the failure can occur in the middle of the execution, be caught by the code and then other subsequent parts of the code may generate new errors as consequences of the first one. 
Similarly, the first error of a log is not always the cause of a failure. 
Sometimes errors successfully caught and handled are logged anyway. 
Thus, it is impossible to extract accurately the error responsible for a failed execution. 
Therefore, we investigated the nature of errors globally, without distinction between error messages in a log.

#todo()[alt text for rasta-heatmap]

#figure(
  image(
    "figs/repartition-of-error-types-among-tools.svg",
    width: 100%,
    alt: "",
  ),
  caption: [Heatmap of the ratio of errors reasons for all tools for the Rasta dataset],
) <fig:rasta-heatmap>

@fig:rasta-heatmap draws the most frequent error objects for each of the tools. 
A black square is an error type that represents more than 80% of the errors raised by the considered tool.
In between, gray squares show a ratio between 20% and 80% of the reported errors. 

First, the heatmap helps us to confirm that our experiments is running in adequate conditions. 
Regarding errors linked to memory, two errors should be investigated: `OutOfMemoryError` and `StackOverflowError`. 
The first one only appears for gator with a low ratio. 
Several tool have a low ratio of errors concerning the stack. 
These results confirm that the allocated heap and stack is sufficient for running the tools with the Rasta dataset. 
Regarding errors linked to the disk space, we observe few ratios for the exception `IOException`, `FileNotFoundError` and `FileNotFoundException`.
Manual inspections revealed that those errors are often a consequence of a failed apktool execution.

Second, the black squares indicate frequent errors that need to be investigated separately. 
In the next subsection, we manually analysed, when possible, the code that generates this high ratio of errors and we give feedback about the possible causes and difficulties to write a bug fix.

=== Tool by Tool Investigation // <sec:rasta-tool-by-tool-inv>
/*
Dialdroid: TODO
  com.google.common.util.concurrent.ExecutionError -> memory error: java.lang.StackOverflowError, java.lang.OutOfMemoryError: Java heap space, java.lang.OutOfMemoryError: GC overhead limit exceeded
%%   java.lang.RuntimeException: 'No call graph present in Scene. Maybe you want Whole Program mode (-w).',  'There were exceptions during IFDS analysis. Exiting.' 'Could not find method'


Didfail: DONE ?
  java.lan.RuntimeException: "Could not find method" (1603),  "not found: java.io.Serializable" (1362) ?, mostly originate from somewhere in soot
  null pointer: mostly originate from somewhere in soot
  File not found: error raised after a previous tool failed

Gator: DONE
  java.lang.RuntimeException: 'error: expected 1 element for annotation Deprecated. Got 1 instead.' (106 occ), misuse of `soot.dexpler.DexAnnotation.addAnnotation` ? as usual, buried under long list of call to soot, hard to pinpoint the cause.
  java.lang.OutOfMemoryError:
  java.io.IOException: No space left on device (169 occurences)
  brut.androlib.AndrolibException: 198, various apktool, some ppb linked to java.io.IOException No space left on device
  FileNotFoundError: ppb consequence of java.io.IOException: No such file or directory: '/tmp/gator-zxkd65ty/apktool.yml

perfchecker: Done
  java.lang.VerifyError: "Expecting a stackmap frame at branch target ", internet propose that it could be caused by Dexguard obfuscation
  link error: probably problems with android.jar?

redexer:
  "File "src/ext/logging.ml", line 712, characters 12-17: Pattern matching failed": suspicious pattern matching but I don't know caml enough to debug.

saaf: DONE
  brut.androlib.AndrolibException: apktoool 1.5.2, "Could not decode arsc file"
  de.rub.syssec.saaf.model.analysis.AnalysisException: encapsulate the apktool error
  java.io.IOException: 'Expected: 0x001c0001, got: 0x00000000', still apktool
  38635 failures over the total of 38710 failures raise a 'brut.androlib.AndrolibException' apktool error.

wognsen_et_al: 
  brut.androlib.AndrolibException: apktool 1.5.2, "Could not decode arsc file"
  java.io.IOException: "Expected: 0x001c0001, got: 0x00000000|38598", apktool
  java.lang.ArithmeticException: divide by zero, from apktool 'org.jf.dexlib.Code.Format.ArrayDataPseudoInstruction.getElementCount'

Amandroid: TODO
  mainly java.lang.NullPointerException at org.argus.jawa.flow.pta.rfa.ReachingFactsAnalysis.process, line 68, don't speak scala well enought to understand what is null

Anadroid: DONE
  subprocess.calledProcessError: subprocess.check_call([APK_TOOL, \"d\" , \"-f\", \"--no-src\", apk_fp, prj_d])
  java.io.IOException: somewhere in brut.androlib.res.decoder.ARSCDecoder.decode
  brut.androlib.AndrolibException: raise by brut.androlib.res.decoder.ARSCDecoder.decode, somewhere in brut.apktool.Main.main
  
  main error msg for brut.androlib.AndrolibException is "Could not decode arsc file"

  Apktool v1.4.3, released December 8, 2011: two months after the parution of sdk 15
  min_sdk 9 to 13 ~50% of exec failled with "Could not decode arsc file", min_sdk 14 81%, 15 94%, >15 >=98%.

  SELECT min_sdk, COUNT(*)*100/(SELECT COUNT(*) FROM apk AS apk2 WHERE apk2.min_sdk = apk.min_sdk) FROM error INNER JOIN apk ON error.sha256 = apk.sha256 WHERE  tool_name = 'anadroid' AND msg='Could not decode arsc file' GROUP BY min_sdk ORDER BY min_sdk;
  SELECT min_sdk, COUNT(*)*100/(SELECT COUNT(*) FROM apk AS apk2 WHERE apk2.min_sdk = apk.min_sdk) FROM exec INNER JOIN apk ON exec.sha256 = apk.sha256 WHERE  tool_name = 'anadroid' AND tool_status = 'FAILED' GROUP BY min_sdk ORDER BY min_sdk;
  SELECT AVG(cnt), MAX(cnt) FROM (SELECT COUNT(*) AS cnt FROM error WHERE tool_name = 'anadroid' AND msg='Could not decode arsc file' GROUP BY sha256);
*/

#paragraph[Androguard and Androguard_dad][
Surprisingly, while Androguard almost never fails to analyse an APK, the internal decompiler of Androguard (DAD) fails more than half of the time. 
The analysis of the logs shows that the issue comes from the way the decompiled methods are stored: each method is stored in a file named after the method name and signature, and this file name can quickly exceed the size limit (255 characters on most file systems). 
It should be noticed that Androguard_dad rarely fails on the Drebin dataset. 
This illustrates the importance to test tools on real and up-to-date APKs: even a bad handling of filenames can influence an analysis.
]

/*
Androguard: Done
  35 error total, no real pattern, stuff like unexpected ID, uncrowned instructions, ect

Androguard Dad: DONE
  All 33819 OSError are '[Errno 36] File name too long: <file path>': the tool try to create files with the name AND SIGNATURE of the disassembled methods, by the file name can be too long:
     '/mnt/out/in/android/vyapar/paymentgateway/model/PaymentGatewayResponseModel$Data$AccountDetails/PaymentGatewayResponseModel$Data$AccountDetails copy$default (PaymentGatewayResponseModel$Data$AccountDetails String String String String String String String String String String String String String String List I Object)PaymentGatewayResponseModel$Data$AccountDetails.ag'
NullPointerException
dad: SError
*/

#paragraph([Mallodroid and Apparecium])[
Mallodroid and Apparecium stand out as the tools that raised the most errors in one run. 
They can raise more than #num(10000) error by analysis. 
However, it happened only for a few dozen of APKs, and conspicuously, the same APKs raised the same hight number of errors for both tools. 
The recurring error is a `KeyError` raise by Androguard when trying to find a string by its identifier. 
Although this error is logged, it seems successfully handled and during a manual analysis of the execution, both tools seemingly perform there analysis without issue. 
This hight number of occurrences may suggest that the output is not valid. 
Still, the tools claim to return a result, so, from our perspective, we consider those analysis as successful.
For other numerous errors, we could not identify the reason why those specific applications raise so many exceptions. 
However we noticed that Mallodroid and Apparecium use outdated version of Androguard (respectively the version 3.0 and 2.0), and neither Androguard v3.3.5 nor DAD with Androguard v3.3.5 raise those exceptions. 
This suggest the issue has been fixed by Androguard and that Mallodroid and Apparecium could benefit from a dependency upgrade. 
]

/*
Apparecium: DONE
  The KeyError is raised from androguard when a non existing string is queried. It happens for only a few apks (~60), 
  but a lot of times. UnicodeEncodeError happened more frequently (2740 apks), also originate from androguard.
  androguard version 2.0

mallodroid: Done
  KeyError: from androguard `get_raw_string`, but do not lead to crash, 33 crash from androguard parsing xml. (androguard 3.0)
Instruction10x%
*/

#paragraph([Blueseal])[
Because Blueseal rarely log more than one error when crashing, it is easy to identify the relevant error. 
The majority of crashes comes from unsupported Android versions (due to the magic number of the DEX files not being supported by the version of back smali used by Blueseal) and methods whose implementation are not found (like native methods).
]

/*
Blueseal: Done
  Majority of runtimes error: 'No method source set for method <method>' are raised from soot.SceneTransformer.transform() called by edu.buffalo.cse.blueseal.BSFlow.CgTransformer.getDynamicEntryPoints().
  No idea how to fix. Update soot? version unclear ('trunk'...), but copyright up to 2010 so 2010?
*/

#paragraph([Droidsafe and SAAF])[
Our investigation of the most common errors raised by Droidsafe and SAAF showed that they are often preceded by an error from apktool. 
Indeed, #num(28654) runs of Droidsafe and #num(38635) runs of SAAF failed after raising at least one of `brut.androlib.AndrolibException` or `brut.androlib.err.UndefinedResObject`, suggesting that those tools would benefit from an upgrade of apktool.
]

/*
Droidsafe:
  UnknownHostException: 'normal', due to network isolation(?), from sfl4j, no impact on the reste of the tool
  droidsafe.utils.CannotFindMethodException: 'Cannot find or resolve <method>' (eg: android.view.ViewTreeObserver: void removeOnGlobalLayoutListener),
     mostly related to android API. First guest 'normal' as droidsafe model the android API and is not updated since ~SDK 19, but the error is replaced by an
     apktool error for min sdk > 19.: 2.0.0rc2
     eg: android.view.ViewTreeObserver.removeOnGlobalLayoutListener: exist un android.jar for sdk 18 and 18, but no in droidsafe model
     the error does not look fatals (it occurred in finished execution) but is more common on failed execution. (1 to 16 ratio)
     TODO: conclusion?

28957 apk with an apktool error
CannotFindMethodException
*/

#paragraph([Ic3 and Ic3_fork])[
We compared the number of errors between Ic3 and Ic3_fork. 
Ic3_fork reports less errors for all types of analysis which suggests that the author of the fork have removed the outputed errors from the original code: the thrown errors are captured in a generic `RuntimeException` which removes the semantic, making it harder our investigations.
Nevertheless, Ic3_fork has more failures than Ic3: the number of errors reported by a tool is not correlated to the final success of its analysis.  
]

/*
ic3: DONE
  jas.jasError: "Missing arguments for instruction ldc" or "Badly formatted number", old soot or bad dare?
  3778 / 10480 (~30) fails without error logged, probable that we don't capture dare failures. 

ic3_fork: DONE
  java.lang.RuntimeException: "This operation requires resolving level SIGNATURES but <method> is at resolving level DANGLING", and "Could not find method". Yet another case of error lost in a sea of soot
  only 38 failures without error logged

IccTa: Done
  java.lang.RuntimeException: same number of "This operation requires resolving level SIGNATURES..." as ic3_fork, 
    lots of "No method source set for method <method>", half the time this occurs the exec failed (and ~30% of the time it finishes)
    "Could not find method": fail every time, in edu.psu.cse.siis.ic3.SetupApplication.calculateSourcesSinksEntrypoints (and again, a lot of soot stack)
jasError
*/

#paragraph([Flowdroid])[
Our exchanges with the authors of Flowdroid led us to expect more timeouts from too long executions than failed run. 
Surprisingly we only got #mypercent(37,NBTOTAL) of timeout, and a hight number of failures.
We tried to detect recurring causes of failures, but the complexity of Flowdroid make the investigation difficult. 
Most exceptions seems to be related to concurrency. //or display a generic messages. 
Other errors that came up regularly are `java.nio.channels.ClosedChannelException` which is raised when Flowdoid fails to read from the APK, although we did not find the reason of the failure, null pointer exceptions when trying to check if a null value is in a `ConcurrentHashMap` (in `LazySummaryProvider.getClassFlows()`) and `StackOverflowError` from `StronglyConnectedComponentsFast.recurse()`. 
We randomly selected 20 APKs that generated stack overflows in Flowdroid and retried the analysis with 500G of RAM allocated to the JVM. 
18 of those runs still failed with a stack overflow without using all the allocated memory, the other two failed after raising null pointer exceptions from `getClassFlows`. 
This shows that the lack of memory is not the primary cause of those failures. 
]

/*
Flowdroid: TODO java.nio.channels.ClosedChannelException cause or consequence?
  java.nio.channels.ClosedChannelException: mosly the zip file reader that refuse an access (after another crash? hard to check)
  java.lang.StackOverflowError: 
  java.lang.RuntimeException: mostly "There were exceptions during IFDS analysis. Exiting."
  java.lang.NullPointerException: soot.jimple.infoflow.collect.ConcurrentHashSet.contains, from soot.jimple.infoflow.methodSummary.data.provider.LazySummaryProvider.getClassFlows
  com.google.common.util.concurrent.ExecutionError: "java.lang.StackOverflowError"


No hidden timeout, what do we believe? avg(time) = 80s, 30s when finished, 137 when failed, max(time) = 3639s when failed, 3284 when finished, 72% of the failures took less than a minute, 93% less than 10, 92% of failed exception raised a NullPointerException.

Pauck: Flowdroid avg 2m on DIALDroid-Bench (real worlds apks)
*/

As a conclusion, we observe that a lot of errors can be linked to bugs in dependencies. 
Our attempts to upgrade those dependencies led to new errors appearing: we conclude that this is a no trivial task that require familiarity with the inner code of the tools.