Mining Quantified Temporal Rules: Formalism, Algorithms, and Evaluation
Libraries usually impose constraints on how clients should use them. Often these constraints are not well-documented. In this paper, we address the problem of recovering such constraints automatically, a problem referred to as specification mining. Given some client programs that use a given library...
Saved in:
Main Authors: | , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2012
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/1345 https://ink.library.smu.edu.sg/context/sis_research/article/2344/viewcontent/Mining_quantified_temporal_rules_Formalism__algorithms__and_evaluation.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-2344 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-23442018-02-07T08:34:54Z Mining Quantified Temporal Rules: Formalism, Algorithms, and Evaluation LO, David RAMALINGAM, Ganesan RANGANATH, Venkatesh Prasad VASWANI, Kapil Libraries usually impose constraints on how clients should use them. Often these constraints are not well-documented. In this paper, we address the problem of recovering such constraints automatically, a problem referred to as specification mining. Given some client programs that use a given library, we identify constraints on the library usage that are (almost) satisfied by the given set of clients.The class of rules we target for mining combines simple binary temporal operators with state predicates (composed of equality constraints) and quantification. This is a simple yet expressive subclass of temporal properties (LTL formulae) that allows us to capture many common API usage rules. We focus on recovering rules from execution traces and apply classical data mining concepts to be robust against bugs (API usage rule violations) in clients. We present new algorithms for mining rules from execution traces. We show how a propositional rule mining algorithm can be generalized to treat quantification and state predicates in a unified way. Our approach enables the miner to be complete (i.e. , mine all rules within the targeted class that are satisfied by the given traces) while avoiding an exponential blowup.We have implemented these algorithms and used them to mine API usage rules for several Windows APIs. Our experiments show the efficiency and effectiveness of our approach. 2012-06-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/1345 info:doi/10.1016/j.scico.2010.10.003 https://ink.library.smu.edu.sg/context/sis_research/article/2344/viewcontent/Mining_quantified_temporal_rules_Formalism__algorithms__and_evaluation.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Specification mining Temporal rules Quantification Dynamic analysis Reverse engineering Software Engineering |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Specification mining Temporal rules Quantification Dynamic analysis Reverse engineering Software Engineering |
spellingShingle |
Specification mining Temporal rules Quantification Dynamic analysis Reverse engineering Software Engineering LO, David RAMALINGAM, Ganesan RANGANATH, Venkatesh Prasad VASWANI, Kapil Mining Quantified Temporal Rules: Formalism, Algorithms, and Evaluation |
description |
Libraries usually impose constraints on how clients should use them. Often these constraints are not well-documented. In this paper, we address the problem of recovering such constraints automatically, a problem referred to as specification mining. Given some client programs that use a given library, we identify constraints on the library usage that are (almost) satisfied by the given set of clients.The class of rules we target for mining combines simple binary temporal operators with state predicates (composed of equality constraints) and quantification. This is a simple yet expressive subclass of temporal properties (LTL formulae) that allows us to capture many common API usage rules. We focus on recovering rules from execution traces and apply classical data mining concepts to be robust against bugs (API usage rule violations) in clients. We present new algorithms for mining rules from execution traces. We show how a propositional rule mining algorithm can be generalized to treat quantification and state predicates in a unified way. Our approach enables the miner to be complete (i.e. , mine all rules within the targeted class that are satisfied by the given traces) while avoiding an exponential blowup.We have implemented these algorithms and used them to mine API usage rules for several Windows APIs. Our experiments show the efficiency and effectiveness of our approach. |
format |
text |
author |
LO, David RAMALINGAM, Ganesan RANGANATH, Venkatesh Prasad VASWANI, Kapil |
author_facet |
LO, David RAMALINGAM, Ganesan RANGANATH, Venkatesh Prasad VASWANI, Kapil |
author_sort |
LO, David |
title |
Mining Quantified Temporal Rules: Formalism, Algorithms, and Evaluation |
title_short |
Mining Quantified Temporal Rules: Formalism, Algorithms, and Evaluation |
title_full |
Mining Quantified Temporal Rules: Formalism, Algorithms, and Evaluation |
title_fullStr |
Mining Quantified Temporal Rules: Formalism, Algorithms, and Evaluation |
title_full_unstemmed |
Mining Quantified Temporal Rules: Formalism, Algorithms, and Evaluation |
title_sort |
mining quantified temporal rules: formalism, algorithms, and evaluation |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2012 |
url |
https://ink.library.smu.edu.sg/sis_research/1345 https://ink.library.smu.edu.sg/context/sis_research/article/2344/viewcontent/Mining_quantified_temporal_rules_Formalism__algorithms__and_evaluation.pdf |
_version_ |
1770570973010984960 |