Questions

AQL-Queries & -Questions

AQL-Questions can be used to ask various analysis tools for certain analysis subjects in a general way. AQL-Queries represent compositions of AQL-Questions. All possible AQL-Queries are defined by this grammar.

AQL-Questions

Basically an AQL-Question always has the following structure:
<Analysis Subject> <Analysis Target> <Ending Symbol>

Optionally with, features (or uses) can be specified:
<Analysis Subject> <Analysis Target> (<Features>)? (<Uses>)? (<With>)? <Ending Symbol>

In the following each of these elements are described in more detail.

Analysis Subjects (Subject of interest - SOI)

Each question can ask for one of the following analysis subjects:

• Arguments: To ask for arbitrary information.
• Flows: A flow symbolizes the transfer of information from one program location to another. To describe such a flow, these two locations have to be specified.
• Intents: Intents are used for inter-component communication, where one component sends an intent to another component. In case of an explicit intent the receiver can be identified by a component reference. But in case of an implicit intent the receiver needs to be recognized through the information triple action, category and data.
• IntentFilters: Specifies the types of intents that an activity, service, or broadcast receiver can respond to.
• IntentSinks: Intent-sinks are special intents, so they can be described in the same way as intents can be described. The difference is that intent-sinks must always come with a reference to a program location (Required to connect answers -- See CONNECT operator).
• IntentSources: Intent-sources represent the counterpart of intent-sinks. An intent-source might be the starting location of an information flow path. They can be described just like intent-sinks and intents with one small but important difference: The reference has to refer to a statement that, for instance, extracts information from an intent. (Also required to connect answers -- See CONNECT operator).
• Permissions: Shows which permissions are used in a certain reference (e.g. an entire app or a specific component).
• Sinks: Collect sinks (statements that leak information to the outside) from an analysis target. Sinks are represented through references.
• Slice: Compute a program slice based on the analysis target (in this case slicing criteria) provided.
• Sources: Collect sources (statements that extract sensitive information) from an analysis target. Sources are represented through references.

Analysis Target (Reference)

The analysis target is specified by a chain consisting of the following elements
Statement -> Method -> Class -> App
In such a chain the elements Statement, Method and Class are optional. In a question we can ask for information inside one target (IN) or for information between two targets (FROM ... TO). Furthermore, preprocessors can be assigned to be applied on apps.

Ending symbols

Any question contained in a query ends with one of the following symbols: ?, ! or ..

• ?: As answer an AQL-Answer is expected,
• !: A file of any type is expected as answer,
• .: The content contained in a file is used as answer.

AQL-Queries

An AQL-Query can be a single or multiple questions combined or not via operators. An operator is always put around one or more questions. A non-trivial (more than one question only) query usually has the following structure:
<Operator> [ <Question(s)> ] <Ending Symbol>

Operators

The following operators are specified in the AQL and implemented in the AQL-System, hence, these operators are also called default operators.

• FILTER: This operator can be used in various ways.
  • When used without specifying a specific filter, it outputs the input set, but beforehand it removes all elements (permissions, intent-sinks and -sources, ...) whose reference does not appear in any flow contained in the answer. Elements without a reference are kept.
  • When an analysis subject is given as filter, the operator filters out all elements of the selected subject of interest.
  • When using a name-value-pair as filter, only the elements that contain this name-value-pair as attribute are kept.
  • A reference can also be used as filter. Only elements that refer to this reference are kept then.
• UNIFY: Collects all information from different AQL-Answers and puts it into one.
• INTERSECT: Extracts the information that appears in all AQL-Answers provided.
• MINUS: Takes the information contained in one AQL-Answer and removes the information also contained in another.
• CONNECT: Works as UNIFY, however, it additionally computes transitive flows and flows that can be determined by connecting intent-sinks with intent-sources. Additionally, incomplete intents-sources (only naming a component) are completed by matching them with intent-filters (naming the same component). Lastly, it adds backward flows whenever there is a intent-sink connected to an intent-source, e.g. from setResult(..) in the intent-source's component to another intent-source in the onActivityResult(..) method of the intent-sink's component.
• CONNECT~: Same as CONNECT but while connecting intent-sinks with intent-sources only the intent's and intent filter's action is taken into account (category and data are ignored).
• SIGN: Automatically signs the given app (using the scripts and key stored in: data/sign)
• TOFD / TOAD: These two operators transform a single AQL-Answer, holding sources and sinks, into a tool specific Source and Sink file. TOFD to a FlowDroid compatible SourcesAndSinks.txt and TOAD to a AmanDroid compatible TaintSourcesAndSinks.txt.

To identify boundaries of operators, [ and ] are used.

It is also possible to define your own operator (see the configuration tutorial).

Variables

Variables can be used to substitute parts in a following query. For example, variable var1 can refer to query Q. Then $var1 can be used one or multiple times in a following query Q' as a substitute of Q. Thereby, partial queries must not be repeated and large queries can be structured more easily.

Examples

Question Examples

The following question asks for flows inside app A:

Flows IN App('A.apk') ?

The next one for flows between app A and B:

Flows FROM App('A.apk') TO App('B.apk') ?

To ask for the permission(s) used by a specific statement inside app A, the following question can be constructed:

Permissions IN Statement(sendTextMessage(..))->App('A.apk') ?

Let us assume we got a preprocessor associated with the keyword TEST. To ask for Intents in a preprocessed version of A we formulate:

Intents IN App('A.apk' | 'TEST') ?

To influence the tool selection a specific tool can be chosen:

Flows IN App('A.apk') USES 'AwesomeDroid' ?

Also the version can be attached (<name>-<Version>):

Flows IN App('A.apk') USES 'AwesomeDroid-1.3.3.7' ?

Or the tool with the highest priority for a certain set of features can be selected:

Flows IN App('A.apk') FEATURING 'TEST', 'Awesome' ?

Asking for a Slice of app A can be done as follows:

Slice FROM
	Statement('from()')->Method('a()')->Class('A')->App('A.apk') 
TO
	Statement('to()')->Method('b()')->Class('B')->App('A.apk')
!

Having such a slice we could ask for flows in it:

Flows IN App({
	Slice FROM
		Statement('from()')->Method('a()')->Class('A')->App('A.apk') 
	TO
		Statement('to()')->Method('b()')->Class('B')->App('A.apk')
	!
}) ?

To simplify such queries variables can be used (e.g. var1):

var1 = {
	Slice FROM
		Statement('from()')->Method('a()')->Class('A')->App('A.apk') 
	TO
		Statement('to()')->Method('b()')->Class('B')->App('A.apk')
	!
}

Flows IN App($var1) ?

By using WITH queries can be constructed that reuse information of other queries:

Flows IN App('A.apk') WITH 'Sources' = {
	Sources IN App('A.apk') ? 
} ?

of course also constants can be used:

Flows IN App('A.apk') WITH 'num' = '42' ?

Here is an example that may forward a source and sink list to let's say FlowDroid:

Flows IN App('A.apk') WITH 'SourcesAndSinks' = {
	TOFD [ 
		UNIFY [
			Sources IN App('A.apk') ?,
			Sinks IN App('A.apk') ?
		] ?
	] !
} USING 'FlowDroid' ?

Another example that uses a question ending with .:

Flows IN App('A.apk') FEATURING {
	Arguments IN App('A.apk') .
} ?

Query Examples

Let us assume we want to know which permission protected statements are connected. The question we could ask is:

UNIFY [
	Flows IN App('A.apk') ?,
	Permissions IN App('A.apk') ?
] ?

Assuming we downloaded an answer telling us which permission uses can be found in app A we could use the following query:

UNIFY [
	Flows IN App('A.apk') ?,
	'downloaded_permission_answer.xml' !
] ?

We could further filter this result by adding the FILTER operator. In this case we would only get Permissions that are somehow related to at least one flow:

FILTER [
	UNIFY [
		Flows IN App('A.apk') ?,
		Permissions IN App('A.apk') ?
	] ?
] ?

To connect two answers determined for two different apps (A, B) the CONNECT operator can be used. Thereby, flows are generated for each pair of matching intent-sinks and -sources:

CONNECT [
	IntentSinks IN App('A.apk') ?,
	IntentSources IN App('B.apk') ?
] ?

Similarly, based on the component specified for intent-filters and -sources, they can complete each other by applying the connect operator:

CONNECT [
	IntentFilters IN App('A.apk') ?,
	IntentSources IN App('B.apk') ?
] ?

The CONNECT operator can also be used to compute the transitive closure of a set of flows:

CONNECT [
	Flows IN App('A.apk') ?
] ?

Transformation Example

The AQL-System also allows to configure transformation rules to declare more complex analysis strategies hidden in a simple query. To that effect the following query:

Flows FROM App('A.apk') TO App('B.apk') ?

may be transformed into:

FILTER [
	CONNECT [
		Flows IN App('A.apk')?,
		Flows IN App('B.apk')?,
		CONNECT [
			IntentSinks IN App('A.apk') ?,
			IntentSources IN App('B.apk') ?
		] ?
	] ?
] ?

(see Rules for more information)