Supervised and Guided Mining of Linear Properties of Android Applications

Abstract:

Our goal is mining linear properties for practical software.
We base our research on supervised learning and allow
the users to supply both positive traces and negative traces of
their software.
We present a variation of dynamic logics for the specification
of both arithmetic and temporal properties.
We then employ genetic programming (GP) to evolve complicate properties
with the ingredient of randomness.
We propose three techniques to guide the GP evolution.
Firstly, we partition the task of supervised learning
into subtasks according to the clustering result of the negative traces.
Secondly, we use formula templates suggesting
what forms of properties are likely to be useful.
Thirdly, we embody several heuristics in the design of
the fitness function based on observations on user behaviors
with hand-held devices.
Finally, we report our experiment with Android hand-held devices.
We carefully design our implementation to help users in avoiding
expensive test instrumentation to their software under test.
We were able to mine properties that reveal anomalies in Facebook.
¡@