| title | date |
|---|---|
GSoC-2021-ShengFengLu |
2021-08-17 08:12:03 -0700 |
My name is Sheng-Feng Lu. I am a fourth-year CS undergraduate student at NSYSU, Taiwan. This summer, I participated in a Google Summer of Code project under the Honeynet Project and I contributed to Quark-Engine, an Android malware storyteller. The two main goals of my project are 1. To rewrite the core library of Quark with Rizin and 2. Evaluate and improve the performance of Quark Engine.
The following section is the summary of 9 important works I've done and their impacts. Also, works like #3, #4, #5, #6, and #8 need to be highlighted since they reached huge milestones for Quark Engine.
-- Work: 96 test cases are added and 19 test cases are improved.
-- Impact: Great tests can protect the correctness of the program so that the original function will not be error-prone when refactoring or modifying.
-- Related Issue: Issue #1
-- Related PRs: PR #189, PR #182
-- Details: Go to details on this page.
-- Work #1: Behavior Map is implemented.
-- Work #2: Rule classification report is enhanced with information such as relationships between behaviors.
-- Impact: By reading the behavior map, users can have an overview of the relationships between suspicious behaviors in the targeted APK file.
-- Related Issue: Issue #191
-- Related PR: PR #192
-- Details: Go to details on this page.
-- Work: Implement an abstract class for Quark core libraries such as apkinfo.py and rzapkinfo.py.
-- Impact: This helps to define essential methods of the Quark core library and reduces a lot of repetitive work in developing new core libraries.
-- Related PRs: PR #194, PR #197, PR #203
-- Details: Go to details on this page.
-- Work: Implement Quark's new core library (rzapkinfo.py) with Rizin.
-- Impact: Androguard is one of the libraries used by Quark to analyze APKs, and it is rarely maintained now. Therefore, we decided to replace Androguard with Rizin. Rizin is a more active binary analysis framework that can help Quark maintain stability.
-- Related Issue: Issue #1276
-- Related PRs: PR #1303, PR #205, PR #209
-- Details: Go to details on this page.
-- Work: 227 bytecode instructions are newly implemented! Only 19 bytecode instructions were implemented before this project.
-- Impact: More behaviors are detected since we implemented almost all bytecode instructions.
-- Related Issue: Issue #131
-- Related PR: PR #207
-- Details: Go to details on this page.
-- Work: We implement a feature that checks whether a class is inherited from another class.
-- Impact: With this feature, Quark can detect inheritance methods usage.
-- Related PR: PR #210
-- Details: Go to details on this page.
-- Work: We have implemented a feature that can support detecting the parameters of the Android API.
-- Impact: With this feature implemented, Quark can now figure out if resources like SMS, call logs, or any other sensitive information is targeted.
-- Related PR: PR #212
-- Details: Go to details on this page.
-- Work: Tools like Flame Graph, Austin, Yappi, and Guppy3 were used to evaluate to performance of Quark. Two performance bottlenecks were found.
-- Impact: With these two bottlenecks resolved, Rizin Core Library: CPU time saves up to 59.20% on average, memory usage saves up to 22.27% on average. Androguard Core Library: CPU time saved up to 23.95% on average.
-- Related PRs: PR #231, PR #232
-- Details: Go to details on this page.
-- Work: We implemented parallelized techniques for Quark analysis.
-- Impact: With this technique, the analysis performed on large APK is improved. The improvement is suitable to apply when users encounter speed issues on Quark.
-- Related PRs: PR #231, PR #232
-- Details: Go to details on this page.
To improve existing test cases and develop a new Rizin-based core library in a test-driven development. I added several test cases based on two guidelines 1. Boundary value analysis and 2. Equivalence class partitioning to improve efficiency and have more comprehensive test cases.
A total of 96 test cases have been added and 19 existing test cases have been improved. Quark's overall test coverage is now 79% (an increase of 10%).
Relative Issue:
Gsoc2021-ShengFengLu Issue #1: Enrich Quark tests
Relative PRs:
Quark-Engine PR #189: Refactor/enrich the rest of Quark's tests
Quark-Engine PR #182: Refactor/enrich the tests of the analysis part of modules
We are committed to providing users with more insightful information. Therefore, by developing a behavior map, users can have an overview of the relationship between suspicious behaviors of different functions in the target APK. Also, these relationships could be found in the rule classification report. Please see figure 2.1. and figure 2.2. for more details.
Relative Issue:
Quark-Engine Issue #191: Show Parent Functions' Cross-References in Rule Classification
Relative PR:
Quark-Engine PR #192: Show Parent Functions' Cross-References In Rule Classification
To have the Rizin based core library co-exist with the Androguard based core library and to ensure the resilience of Quark, I implemented an abstract class for Quark core libraries. Figure 3.1. is a glance at the source code of the abstract class. Please go here for the complete source code.
Relative PRs:
Quark-Engine PR #194: Add A Standard Interface for Accessing APK Information
Quark-Engine PR #197: Clean Up the Direct Use of MethodAnalysis
Quark-Engine PR #203: Make Apkinfo implement the standard APK interface
Currently, many features in Quark-Engine rely on Androguard for analysis. However, Androguard remained inactive in the past two years. Therefore, to keep Quark's resilience, we choose Rizin, a more active reverse engineering framework open source project, as Quark's new core library.
During development, two issues were encountered while implementing the Rizin core library. 1. The result of Xref is incorrect in some cases 2. It doesn't support multiple dex file analysis.
We reported these two issues to the Rizin community. For the Xref issue, the community proved that it is the bug of Rizin itself and they put this issue to be resolved. As for the multi-dex analysis issue, the community now has this problem fixed.
Here is a video demonstrating a Quark analysis of the Rizin-based library.
Relative Issue:
Rizin Issue #1276: Missing method references in DEX
Relative PRs:
Rizin PR #1303: Load all dalvik files in an APK
Quark-Engine PR #205: Add a Rizin-based core library
Quark-Engine PR #209: Update travis.yml to set up Rizin
In the previous version of Quark, the Dalvik bytecode loader supported only two types of bytecodes. The lack of bytecodes may cause false positives in tainted analysis.
Therefore, one of my goals is to improve accuracy by adding the missing 227 bytecodes to the loader. All added bytecodes are related to the data flow between the registers. Now the Dalvik bytecode loader supports bytecode types such as array/exception accessing, function calls, and arithmetic operations.
And surprisingly, this had improved the analysis accuracy. We use 14d9f1a92dd984d6040cc41ed06e273e.apk to test this implementation. Experiment results show the confidence of detected behavior increased 20%. See Figure 5.1. and Figure 5.2. for more details.
Relative Issue:
Quark-Engine Issue #131: Improve Quark's tainted analysis accuracy in stage 5
Relative PR:
Quark-Engine PR #207: Improve the tainted analysis of Quark
Class inheritance checking is not supported by the previous versions of Quark. However, it is quite essential when detecting Android API usage.
Therefore, I implemented a patch to deal with this problem. Three things were implemented in this patch:
1. Track the data type of each register in the bytecode loader.
2. Construct a class inheritance relation dictionary in pyeval.py.
3. Add a lookup procedure to check the inheritance relationship to the loader.
And surprisingly, this had improved the analysis accuracy. We use 14d9f1a92dd984d6040cc41ed06e273e.apk to test this implementation. Experiment results show the confidence of detected behavior increased 20%. See Figure 6.1. and Figure 6.2. for more details.
Relative PR:
Quark-Engine PR #210: Enhance the Simulation Accuracy of the Bytecode Loader
Many Android APIs represent different behaviors based on parameters. However, in the previous versions of Quark, it could not check Android API parameters, which always need manual checks when analyzing malware.
Therefore, by implementing this feature, Quark can now determine whether the malware gathers personal information such as SMS, call logs, or any other sensitive information.
This implementation lets users fill in keywords like targeted resources (SMS, Calllog) in the detection rule.
And surprisingly, this had improved the analysis accuracy. We use 14d9f1a92dd984d6040cc41ed06e273e.apk to test this implementation. Experiment results show that the API parameters check with the new rule. See Figure 7.1. and Figure 7.2. for more details.
Relative PR:
Quark-Engine PR #212: Add an Optional Parameter Filter For JSON Rules
According to user feedback, Quark encounters performance problems when analyzing large-size APKs. Therefore, we choose several performance evaluation tools such as Flame Graph, Austin, Yappi, and Guppy3 to find performance problems and solve them.
Our evaluation is quite simple, we take CPU time and memory usage as the indicators to evaluate the performance of Quark's two core libraries (apkinfo.py, rzapkinfo.py). 3 sample APKs were chosen based on different file sizes to conduct the evaluation.
8.1. Core Library based on Androguard
CPU time - Androguard based core library
In this section, we use 3 sample APKs sizes ranged from 1MB, 4MB, and 10MB to evaluate the CPU time of the Androguard based core library. All 3 APKs are from the database of the University of Luxembourg, AndroZoo, and flagged as malware by VirusTotal. We use Flame Graph to generate 3 figures below. All figures point to one problem, that is, ==find_method()== in apkinfo.py occupied most of the CPU times. See Figure 8.1., Figure 8.2. and Figure 8.3. for more details.
Memory Usage - Androguard based core library
In this section, the same sample APKs were used to evaluate the memory usage of the Androguard based core library. We use Flame Graph to generate 3 figures below. All figures point to one problem: most of the memory was consumed when parsing APKs with Androguard. See Figure 8.4., Figure 8.5. and Figure 8.6. for more details.
8.2. Core Library based on Rizin
CPU time - Rizin based core library
In this section, the same sample APKs were used to evaluate the CPU time of the Rizin based core library. We use Flame Graph to generate 3 figures below. All figures point to one problem, that is, repeated calculation of unchanging results. And we found out that 3 methods have this problem. They're ==all_methods()==, ==permission()==, and ==class_hierarchy()== in rzapkinfo.py. See Figure 8.7., Figure 8.8. and Figure 8.9. for more details.
Memory Usage - Rizin based core library
In this section, the same 3 sample APKs were used to evaluate the memory usage of Rizin based core library. We use Flame Graph to generate 3 figures below. All figures point to one problem, that is, duplicate Rizin processes. And we found out that 1 method has this problem. It is ==permission()== in rzapkinfo.py. Note that ==permission()== is invisible in the last figures since massive objects are created in the third-party method, ==cmdj()==.
8.3. Solutions to Problems found
Androguard based core library
- CPU Time: We implemented a patch to apkinfo.py to fix this problem.
- Memory Usage: The solution, for now, is the Rizin core library. We arrange to help Androguard solving it in the future.
Rizin based core library
- CPU Time: We implemented a patch to rzapkinfo.py to this problem.
- Memory Usage: This problem is solved by the same patch we submitted.
8.4. Performance Re-assessments
Androguard based core library
After implemented the patch, the CPU time saved up to 23.95% on average.
| MD5 | Size (MB) |
Before The Improvement (second) |
After The Improvement (second) |
Percentage increase (%) |
|---|---|---|---|---|
| 9283c74dd8356c18bb6d94b88b8fdd9b | 1 | 2.00 | 1.58 | 26% |
| 8e241d9a7a7cf8bf606b15a9f43af5fd | 5.3 | 3.47 | 2.91 | 16.13% |
| 3edfc78ab53521942798ad551027d04f | 10 | 60.53 | 42.53 | 29.73% |
Rizin based core library
After implemented the patch, the CPU time saved up to 59.20% on average.
| MD5 | Size (MB) |
Before The Improvement (second) |
After The Improvement (second) |
Percentage (%) |
|---|---|---|---|---|
| 9283c74dd8356c18bb6d94b88b8fdd9b | 1 | 5.56 | 1.24 | 77.70% |
| 8e241d9a7a7cf8bf606b15a9f43af5fd | 5.3 | 21.47 | 12.60 | 41.31% |
| 3edfc78ab53521942798ad551027d04f | 10 | 1118.00 | 462.90 | 58.60% |
After implemented the patch, the memory usage saved up to 22.27% on average.
| MD5 | Size (MB) | Before The Improvement (MB) | After The Improvement (MB) | Percentage (%) |
|---|---|---|---|---|
| 9283c74dd8356c18bb6d94b88b8fdd9b | 1 | 285.00 | 211.76 | 25.70% |
| 8e241d9a7a7cf8bf606b15a9f43af5fd | 5.3 | 278.19 | 235.63 | 15.30% |
| 3edfc78ab53521942798ad551027d04f | 10 | 1116.40 | 828.11 | 25.82% |
Relative PRs:
Quark-Engine PR #231: Cache commonly used attributes in the Rizin core library
Quark-Engine PR #232: Simplify the generator value check in the Androguard core library
Androguard based core library
The improvement is significant on large APKs. However, the cost of process initialization makes it not obvious when analyzing small ones. I conclude that the improvement is suitable to apply when users encounter speed issues on Quark. See Table 9.1. for more details.
| MD5 | Size (MB) |
Before The Improvement (Second) |
After The Improvement (Second) |
Percentage (%) |
|---|---|---|---|---|
| 9283c74dd8356c18bb6d94b88b8fdd9b | 1 | 2.90 | 2.04 | 29.65% |
| 8e241d9a7a7cf8bf606b15a9f43af5fd | 5.3 | 3.04 | 4.10 | -34.87% |
| 3edfc78ab53521942798ad551027d04f | 10 | 69.32 | 42.30 | 38.98% |
Rizin based core library
The improvement is significant on large APKs. However, the cost of process initialization makes it not obvious when analyzing small ones. I conclude that the improvement is suitable to apply when users encounter speed issues on Quark. See Table 9.2. for more details.
| MD5 | Size (MB) | Before The Improvement (Second) | After The Improvement (Second) | Percentage (%) |
|---|---|---|---|---|
| 9283c74dd8356c18bb6d94b88b8fdd9b | 1 | 1.24 | 1.70 | -37.09% |
| 8e241d9a7a7cf8bf606b15a9f43af5fd | 5.3 | 21.47 | 12.60 | 41.31% |
| 3edfc78ab53521942798ad551027d04f | 10 | 462.90 | 36.93 | 92.02% |
Relative PRs:
Quark-Engine PR #223: Parallelize the analysis
- Keep assisting the Rizin community with the Xref issue in APKs.
- Address the Androguard memory problem we found and help Androguard to solve it.
- Continuously improve the Rizin core library to make its performance better than the Androguard core library.
Thank my mentors, JunWei Song and KunYu Chen, for their sincere support and guidance.
Thank Androguard and Rizin for helping me reach my goal.
Thank TTC for providing me the working environment.
Thank Honeynet Project for this great opportunity.
Thank Google for making all this happend!