1,720,981 research outputs found
Fault localization based on information flow coverage
No full textFailures triggered by hard to debug defects usually involve complex interactions between many program elements. This paper hypothesizes that information flows present a good model for such interactions and presents a new fault localization technique based on information flow coverage. Using a test suite, the technique ranks the statements in a program in terms of their likelihood of being faulty by comparing the information flows induced by the failing runs with the ones induced by the passing runs. The ranking of the statements associated with a given flow is primarily determined by contrasting the percentage of failing runs to the percentage of passing runs that induced it. Generally, a higher percentage of failing runs implies a higher rank. To show its potential, the technique was applied to several open-source Java programs and was compared, with respect to its fault localization effectiveness, with three other coverage techniques that use similar style metrics that are defined for statements, branches, and def-use pairs, respectively. The results revealed that information flow, branch, and def-use coverage performed consistently better than statement coverage. In addition, in a considerable number of cases information flow coverage performed better than branch and def-use coverage. Specifically, it was always safer but not always more precise. Copyright © 2009 John Wiley and Sons, Ltd.Agrawal H., 1995, ISSRE 95, P143; AGRAWAL H, 1990, SIGPLAN NOTICES, V25, P246; *BCEL, 2003, AP JAK PROJ; Binkley D, 2004, ADV COMPUT, V62, P106; Clause J, 2007, PROC INT CONF SOFTW, P261; Cleve H, 2005, PROC INT CONF SOFTW, P342; DALLMEIER V, 2005, INT S AUT AN DRIV DE, P99; DENMAT T, 2005, INT C AUT SOFTW ENG, P396; Denning D. E., 1982, CRYPTOGRAPHY DATA SE; DENNING DE, 1977, COMMUN ACM, V20, P504, DOI 10.1145-359636.359712; Do HS, 2005, EMPIR SOFTW ENG, V10, P405, DOI 10.1007-s10664-005-3861-2; FENTON JS, 1974, COMPUT J, V17, P143, DOI 10.1093-comjnl-17.2.143; Harman M, 2006, INFORM SOFTWARE TECH, V48, P549, DOI 10.1016-j.infsof.2005.06.001; Jones J., 2001, P 24 INT C SOFTW ENG, P467; Jones J. A., 2005, P 20 IEEE ACM INT C, P273, DOI 10.1145-1101908.1101949; Jones J. A., 2007, ISSTA 07, P16; KOREL B, 1994, ISSTA, P66; Liblit B., 2003, P ACM SIGPLAN 2003 C, P141; LIBLIT B., 2005, P 2005 ACM SIGPLAN C, P15, DOI 10.1145-1065010.1065014; Liu C, 2006, IEEE T SOFTWARE ENG, V32, P831; Masri W, 2008, EMPIR SOFTW ENG, V13, P369, DOI 10.1007-s10664-008-9071-y; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; MASRI W, 2006, 4 INT WORKSH DYN AN, P73; MASRI W, 2005, 2005 WORKSH SOFTW EN, P1; MASRI W, 2009, ACM T SOFTW IN PRESS; Masri W, 2008, COMPUT SECUR, V27, P176, DOI 10.1016-j.cose.2008.06.002; Masri W, 2004, 15TH INTERNATIONAL SYMPOSIUM ON SOFTWARE RELIABILITY ENGINEERING, PROCEEDINGS, P198, DOI 10.1109-ISSRE.2004.17; Masri W., 2009, INFORM SOFTWARE TECH, V51, P395; Renieres M., 2003, Proceedings 18th IEEE International Conference on Automated Software Engineering; TIP F, 1995, J PROGRAM LANG, V3, P121; WEISER M, 1984, IEEE T SOFTWARE ENG, V10, P352; Xie T, 2005, IEEE T SOFTWARE ENG, V31, P869, DOI 10.1109-TSE.2005.107; ZHANG X, 2006, INT C PROGR LANG DES, P16932211
Generating profile-based signatures for online intrusion and failure detection
No full textContext Program execution profiles have been extensively and successfully used in several dynamic analysis fields such as software testing and fault localization. Objective This paper presents a pattern-matching approach implemented as an application-based intrusion (and failure) detection system that operates on signatures generated from execution profiles. Such signatures are not descriptions of exploits, i.e. they do not depend on the syntax or semantics of the exploits, but instead are descriptions of program events that correlate with the exploitation of program vulnerabilities. Method A vulnerability exploit is generally correlated with the execution of a combination of program elements, such as statements, branches, and definition-use pairs. In this work we first analyze the execution profiles of a vulnerable application in order to identify such suspicious combinations, define signatures that describe them, and consequently deploy these signatures within an intrusion detection system that performs online signature matching. Results To evaluate our approach, which is also applicable to online failure detection, we implemented it for the Java platform and applied it onto seven open-source applications containing 30 vulnerabilities-defects for the purpose of the online detection of attacks- failures. Our results showed that our approach worked very well for 26 vulnerabilities-defects (86.67percent) and the overhead imposed by the system is somewhat acceptable as it varied from 46percent to 102percent. The exhibited average rates of false negatives and false positives were 0.43percent and 1.03percent, respectively. Conclusion Using profile-based signatures for online intrusion and failure detection was shown to be effective. © 2013 Elsevier B.V. All rights reserved.Abou-Assi R., 2011, 1 INT WORKSH TEST DE; Agrawal R., 1993, ACM SIGMOD RECORD, V22, P207, DOI DOI 10.1145-170035.170072; Apiwattanapong T, 2005, PROC INT CONF SOFTW, P432; Bodik P., 2005, Proceedings. Second International Conference on Autonomic Computing; Brumley D., 2007, P 20 IEEE COMP SECUR; Brumley D, 2006, P IEEE S SECUR PRIV, P2, DOI 10.1109-SP.2006.41; Chaturvedi A., 2005, P IEEE S SEC PRIV; Chen HF, 2007, IEEE T SYST MAN CY C, V37, P644, DOI 10.1109-TSMCC.2007.897496; Cohen W.W., 1995, MACH LEARN 12 INT C; DENNING DE, 1976, COMMUN ACM, V19, P236, DOI 10.1145-360051.360056; Do HS, 2005, EMPIR SOFTW ENG, V10, P405, DOI 10.1007-s10664-005-3861-2; El-Ghali M., 2009, 5 INT WORKSH SOFTW E; Ernst MD, 2001, IEEE T SOFTWARE ENG, V27, P99, DOI 10.1109-32.908957; Feng HHP, 2003, P IEEE S SECUR PRIV, P62, DOI 10.1109-SECPRI.2003.1199328; Forrest S, 1996, P IEEE S SECUR PRIV, P120, DOI 10.1109-SECPRI.1996.502675; Giffin JT, 2006, LECT NOTES COMPUT SC, V4219, P41; Graves TL, 2001, ACM T SOFTW ENG METH, V10, P184, DOI 10.1145-367008.367020; Jackson D., 1994, P 2 ACM SIGSOFT S FD; Jones J. A., 2002, Proceedings of the 24th International Conference on Software Engineering. ICSE 2002, DOI 10.1109-ICSE.2002.1007991; Kang D.-K., 2005, P 6 IEEE SYST MAN CY; Kim H.-A., 2004, Proceedings of the 13th USENIX Security Symposium; Kruegel C, 2003, LECT NOTES COMPUT SC, V2808, P326; Lee W, 1998, P 7 USENIX SEC S SAN; Lee W, 1999, IEEE S SECUR PRIV, V7, P120; Leon D., 2000, Proceedings of the 2000 International Conference on Software Engineering. ICSE 2000 the New Millennium, DOI 10.1109-ICSE.2000.870403; Li Z, 2007, IEEE T SOFTWARE ENG, V33, P225, DOI 10.1109-TSE.2007.38; Liepins G., 1989, 12 NAT COMP SEC C BA, P495; Lippmann R, 2000, LECT NOTES COMPUT SC, V1907, P162; Lorenzoli D., 2007, P 18 IEEE INT S SOFT; Mannila H., 1995, P 1 INT C KNOWL DISC; Martin M, 2005, ACM SIGPLAN NOTICES, V40, P365, DOI 10.1145-1103845.1094840; Masri W., 2009, 7 INT WORKSH DYN AN; Masri W., 2012, ENHANCING FAULT LOCA; Masri W, 2008, EMPIR SOFTW ENG, V13, P369, DOI 10.1007-s10664-008-9071-y; Masri W, 2009, INFORM SOFTWARE TECH, V51, P385, DOI 10.1016-j.infsof.2008.05.008; Masri W., 2009, ACM T SOFTWARE ENG M, V19; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; Masri W, 2010, SOFTW TEST VERIF REL, V20, P121, DOI 10.1002-stvr.409; Masri W., 2009, INT WORKSH DEF LARG; Masri W., 2010, 3 INT C SOFTW TEST V; Masri W., 2006, 4 INT WORKSH DYN AN; Masri W, 2008, COMPUT SECUR, V27, P176, DOI 10.1016-j.cose.2008.06.002; Masri W, 2011, J SYST SOFTWARE, V84, P1171, DOI 10.1016-j.jss.2011.02.007; McConnell S., 2004, CODE COMPLETE; Miller Frederic P., 2009, ABANDONWARE COMPUTER; Mutz D., 2006, ACM Transactions on Information and Systems Security, V9, DOI 10.1145-1127345.1127348; Newsome J., 2005, P 12 ANN NETW DISTR; Newsome James, 2006, P 13 S NETW DISTR SY; Nusayr Amjad, 2009, USING AOP DET RUNT M, P8; Parnin C., ISSTA 2011, P199; Portnoy L., 2001, ACM CSS WORKSH DAT M; Sabelfeld A., 2003, IEEE J SEL AREA COMM, V21, P1; Sen K., 2005, 10 EUR SOFTW ENG C; Shull Forrest, 2002, P 8 INT S SOFTW METR; Singh A, 2006, J HEURISTICS, V12, P5, DOI 10.1007-s10732-006-3750-x; Steven S., 2000, 2000 INT S SOFTW TES, P158; Wagner D., 2002, P 9 ACM C COMP COMM, P255; Wagner D, 2001, P IEEE S SECUR PRIV, P156, DOI 10.1109-SECPRI.2001.924296; Xu HZ, 2004, LECT NOTES COMPUT SC, V3224, P21; Yin H, 2007, CCS'07: PROCEEDINGS OF THE 14TH ACM CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY, P11620
Prevalence of coincidental correctness and mitigation of its impact on fault localization
Full text linkThe article examines the prevalence of coincidental correctness and mitigation of its impact on fault localization. Coverage-Based Fault Localization (CBFL) techniques seek to identify failure correlated program elements using test suites in which tests are tagged as failing or passing, that is, elements that are induced by all (or most) failing runs and not induced by any (or most) passing runs; and locate the faulty code using some examination strategy. To evaluate the effectiveness of research techniques, researchers empirically quantified their accuracy in identifying CC tests in test suites involving programs with seeded faults as well as real faults. The results were promising, for example, the better performing technique, using 105 test suites and statement coverage, exhibited 9percent false negatives, 30percent false positives, and no false negatives nor false positives in 14.3percent of the test suites.Abou-Assi R., 2011, P 1 INT WORKSH TEST; Abreu R, 2009, IEEE INT CONF AUTOM, P88, DOI 10.1109-ASE.2009.25; Abreu R, 2009, J SYST SOFTWARE, V82, P1780, DOI 10.1016-j.jss.2009.06.035; Abreu R., 2006, P 12 PAC RIM INT S D, P39, DOI DOI 10.1109-PRDC.2006.18; Agrawal H., 1995, Proceedings. The Sixth International Symposium on Software Reliability Engineering (Cat. No.95TB8129), DOI 10.1109-ISSRE.1995.497652; Ammann P., 2008, INTRO SOFTWARE TESTI; Baudry B., 2006, P 28 INT C SOFTW ENG, P82, DOI 10.1145-1134285.1134299; Cadar C., 2008, P 8 USENIX C OP SYST, P209; Chen M. Y., 2002, Proceedings International Conference on Dependable Systems and Networks, DOI 10.1109-DSN.2002.1029005; Dallmeier V., 2005, P 6 INT S AUT AN DRI, P99, DOI 10.1145-1085130.1085143; Dallmeier V, 2005, LECT NOTES COMPUT SC, V3586, P528; Dickinson W, 2001, PROC INT CONF SOFTW, P339, DOI 10.1109-ICSE.2001.919107; Do HS, 2005, EMPIR SOFTW ENG, V10, P405, DOI 10.1007-s10664-005-3861-2; Han J., 2001, DATA MINING CONCEPTS, P335; Harman M, 2006, INFORM SOFTWARE TECH, V48, P549, DOI 10.1016-j.infsof.2005.06.001; Hierons RM, 2006, ACM T SOFTW ENG METH, V15, P227, DOI 10.1145-1151695.1151696; HOWDEN WE, 1982, IEEE T SOFTWARE ENG, V8, P371, DOI 10.1109-TSE.1982.235571; Jiawei H. M. K., 2001, DATA MINING CONCEPTS, P335; Jones J., 2001, P 24 INT C SOFTW ENG, P467; Jones J., 2007, P 2007 ACM SIGSOFT I, P16, DOI 10.1145-1273463.1273468; Jones J. A., 2005, P 20 IEEE ACM INT C, P273, DOI 10.1145-1101908.1101949; Korels B, 1994, P INT S SOFTW TEST A, P66, DOI 10.1145-186258.186514; Leon D., 2000, Proceedings of the 2000 International Conference on Software Engineering. ICSE 2000 the New Millennium, DOI 10.1109-ICSE.2000.870403; Leon D., 2005, P 16 IEEE INT S SOFT, P311; Liblit B, 2003, ACM SIGPLAN NOTICES, V38, P141, DOI 10.1145-780822.781148; Liblit B, 2005, ACM SIGPLAN NOTICES, V40, P15, DOI 10.1145-1064978.1065014; Liu CJ, 2006, PME CONFERENCE PROCE, P286; Liu C, 2005, SIAM PROC S, P286, DOI 10.1145-1081706.1081753; Liu C, 2006, IEEE T SOFTWARE ENG, V32, P831; Marick B., 1991, P 4 S SOFTW TEST AN, P190, DOI 10.1145-120807.120825; Masri W, 2008, EMPIR SOFTW ENG, V13, P369, DOI 10.1007-s10664-008-9071-y; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; Masri W., 2009, ACM T SOFTW ENG METH, V19, P2; Masri W, 2010, SOFTW TEST VERIF REL, V20, P121, DOI 10.1002-stvr.409; Masri W., 2009, INT WORKSH DEF LARG; Masri W., 2006, P 4 INT WORKSH DYN A; Masri W, 2008, COMPUT SECUR, V27, P176, DOI 10.1016-j.cose.2008.06.002; Masri W, 2011, J SYST SOFTWARE, V84, P1171, DOI 10.1016-j.jss.2011.02.007; Masri W., 2009, INFORM SOFTWARE TECH, V51, P395; Masri W., 2010, P 3 INT C SOFTW TEST; Masri W., 2012, P IEEE 5 INT C SOFTW, P737; Parnin C., 2011, P INT S SOFTW TEST A, P199; Podgurski A, 2003, PROC INT CONF SOFTW, P465, DOI 10.1109-ICSE.2003.1201224; Renieres M., 2003, Proceedings 18th IEEE International Conference on Automated Software Engineering; RICHARDSON DJ, 1993, IEEE T SOFTWARE ENG, V19, P533, DOI 10.1109-32.232020; Santelices R, 2009, PROC INT CONF SOFTW, P56, DOI 10.1109-ICSE.2009.5070508; Singh S., 2011, P NAT C REC TRENDS E; VOAS JM, 1993, J SYST SOFTWARE, V20, P207, DOI 10.1016-0164-1212(93)90064-5; VOAS JM, 1992, IEEE T SOFTWARE ENG, V18, P717, DOI 10.1109-32.153381; Wang X., 2009, P 31 IEEE INT C SOFT, P45; WEISER M, 1984, IEEE T SOFTWARE ENG, V10, P352; Wong E, 2008, P 1 INT C SOFTW TEST, P42; ZADEH LA, 1965, INFORM CONTROL, V8, P338, DOI 10.1016-S0019-9958(65)90241-X; Zheng A. X., 2006, P 23 INT C MACH LEAR, P1105, DOI 10.1145-1143844.1143983; Zoeteweij P., 2007, P TEST AC IND C PRAC, P89; Zoeteweij P., 2007, P 14 C WORKSH ENG CO0
Measuring the strength of information flows in programs
No full textDynamic information flow analysis (DIFA) was devised to enable the flow of information among variables in an executing program to be monitored and possibly regulated. It is related to techniques like dynamic slicing and dynamic impact analysis. To better understand the basis for DIFA, we conducted an empirical study in which we measured the strength of information flows identified by DIFA, using information theoretic and correlation-based methods. The results indicate that in most cases the occurrence of a chain of dynamic program dependences between two variables does not indicate a measurable information flow between them. We also explored the relationship between the strength of an information flow and the length of the corresponding dependence chain, and we obtained results indicating that no consistent relationship exists between the length of an information flow and its strength. Finally, we investigated whether data dependence and control dependence makes equal or unequal contributions to flow strength. The results indicate that flows due to data dependences alone are stronger, on average, than flows due to control dependences alone. We present the details of our study and consider the implications of the results for applications of DIFA and related techniques. © 2009 ACM.AGRAWAL H, 1990, SIGPLAN NOTICES, V25, P246; APIWATTANAPONG T, 2005, P INT C SOFTW ENG ST; Binkley D, 2004, IEEE T SOFTWARE ENG, V30, P715, DOI 10.1109-TSE.2004.78; Bishop M., 2002, COMPUTER SECURITY AR; Box G.E.P., 2005, STAT EXPT DESIGN INN; CLARK D, 2001, P QUANT ASP PROGR LA; CLARK D, 2004, P IFIP WG 1 7 ACM SI; Clause J., 2007, P INT S SOFTW TEST A; Cover TM, 1991, ELEMENTS INFORM THEO; Dallmeier V., 2006, P 4 INT WORKSH DYN A; Denning D. E., 1982, CRYPTOGRAPHY DATA SE; DENNING DE, 1977, COMMUN ACM, V20, P504, DOI 10.1145-359636.359712; DENNING DE, 1976, COMMUN ACM, V19, P236, DOI 10.1145-360051.360056; Do HS, 2005, EMPIR SOFTW ENG, V10, P405, DOI 10.1007-s10664-005-3861-2; FENTON JS, 1974, COMPUT J, V17, P143, DOI 10.1093-comjnl-17.2.143; FERRANTE J, 1987, ACM T PROGR LANG SYS, V9, P319, DOI 10.1145-24039.24041; Kachigan S. K., 1986, STAT ANAL INTERDISCI; Korels B, 1994, P INT S SOFTW TEST A, P66, DOI 10.1145-186258.186514; KRUS D. J, 2006, VISUAL STAT; LAMPSON BW, 1973, COMMUN ACM, V16, P613, DOI 10.1145-362375.362389; Law J, 2003, PROC INT CONF SOFTW, P308, DOI 10.1109-ICSE.2003.1201210; Lieberherr KJ, 2004, PROC INT CONF SOFTW, P2, DOI 10.1109-ICSE.2004.1317408; Lowe TG, 2002, J SPINAL DISORD TECH, V15, P31; MARSI W, 2004, THESIS CASE W RESERV; MASRI W., 2004, P 15 IEEE INT S SOFT; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; Masri W., 2006, P 4 INT WORKSH DYN A; MASRI W, 2005, P SOFTW ENG SEC SYST; MCCAMANT S, 2007, P ACM SIGPLAN WORKSH; MCCAMANT S, 2006, MITCSAILTR2006076; National Institute of Standards and Technology (NIST) Advanced Encryption Standard (AES), 2001, FED INF PROC STAND P, V197; Newsome J., 2005, P NETW DISTR SYST SE; Pearl Judea, 2000, CAUSALITY; PODGURSKI A, 1990, IEEE T SOFTWARE ENG, V16, P965, DOI 10.1109-32.58784; PODGURSKI A, 1989, THESIS U MASSACHUSET; Sabelfeld A, 2003, IEEE J SEL AREA COMM, V21, P5, DOI 10.1109-JSAC.2002.806121; Siegel S., 1956, NONPARAMETRIC STAT B; Sinha S, 2001, ACM T SOFTW ENG METH, V10, P209, DOI 10.1145-367008.367022; Spirtes P., 2000, CAUSALITY PREDICTION; STEVEN S, 2000, P INT S SOFTW TEST A, P158; TIP F, 1995, J PROGRAM LANG, V3, P121; Visser W., 2003, Automated Software Engineering, V10, DOI 10.1023-A:1022920129859; VOAS JM, 1993, J SYST SOFTWARE, V20, P207, DOI 10.1016-0164-1212(93)90064-5; Woodward MR, 2000, P 2000 ACM SIGSOFT I, P168, DOI 10.1145-347324.349016; XIE T, 2006, P 28 INT C SOFTW ENG; Zhang X, 2004, P ACM SIGPLAN C PROG, P94, DOI 10.1145-996841.996855; ZHANG X, 2005, P AADEBUG; ZHANG X, 2006, P PLDI; ZHANG X, 2006, P INT C SOFTW ENG128
An algorithm for capturing variables dependences in test suites
No full textThe use of dynamic dependence analysis spans several areas of software research including software testing, debugging, fault localization, and security. Many of the techniques devised in these areas require the execution of large test suites in order to generate profiles that capture the dependences that occurred between given types of program elements. When the aim is to capture direct and indirect dependences between finely granular elements, such as statements and variables, this process becomes highly costly due to: (1) the large number of elements, and (2) the transitive nature of the indirect dependence relationship. The focus of this paper is on computing dynamic dependences between variables, i.e., dynamic information flow analysis or DIFA. First, because the problem of tracking dependences between statements, i.e., dynamic slicing, has already been addressed by numerous researchers. Second, because DIFA is a more difficult problem given that the number of variables in a program is unbounded. We present an algorithm that, in the context of test suite execution, leverages the already computed dependences to efficiently compute subsequent dependences within the same or later test runs. To evaluate our proposed algorithm, we conducted an empirical comparative study that contrasted it, with respect to efficiency, to three other algorithms: (1) a naïve basic algorithm, (2) a memoization based algorithm that does not leverage computed dependences from previous test runs, and (3) an algorithm that uses reduced ordered binary decision diagrams (roBDDs) to maintain and manage dependences. The results indicated that our new DIFA algorithm performed considerably better in terms of both runtime and memory consumption. © 2011 Elsevier Inc.Agrawal H., 1990, P ACM SIGPLAN 90 C P, P246, DOI DOI 10.1145-93542.93576; *BCEL, 2003, AP JAK PROJ; Beszedes A., 2001, Proceedings Fifth European Conference on Software Maintenance and Reengineering, DOI 10.1109-CSMR.2001.914974; Clause J., 2007, P INT S SOFTW TEST A, P196, DOI 10.1145-1273463.1273490; Cormen T., 2001, INTRO ALGORITHMS; Elbaum S, 2002, IEEE T SOFTWARE ENG, V28, P159, DOI 10.1109-32.988497; El-Ghali M., 2009, 5 INT WORKSH SOFTW E; Farago C., 2002, Acta Cybernetica, V15; FERRANTE J, 1987, ACM T PROGR LANG SYS, V9, P319, DOI 10.1145-24039.24041; HALDAR V, 2005, 0502 U CAL DEP INF C; HARMAN M, 1995, SOFTW TEST VERIF REL, V3, P143; Harrold MJ, 2000, SOFTW TEST VERIF REL, V10, P171, DOI 10.1002-1099-1689(200009)10:3171::AID-STVR2093.0.CO;2-J; KOREL B, 1988, INFORM PROCESS LETT, V29, P155, DOI 10.1016-0020-0190(88)90054-3; Korels B, 1994, P INT S SOFTW TEST A, P66, DOI 10.1145-186258.186514; LAMPSON BW, 1973, COMMUN ACM, V16, P613, DOI 10.1145-362375.362389; Masri W., 2009, 7 INT WORKSH DYN AN; Masri W, 2008, EMPIR SOFTW ENG, V13, P369, DOI 10.1007-s10664-008-9071-y; Masri W, 2009, INFORM SOFTWARE TECH, V51, P385, DOI 10.1016-j.infsof.2008.05.008; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; Masri W, 2010, SOFTW TEST VERIF REL, V20, P121, DOI 10.1002-stvr.409; Masri W, 2009, ACM T SOFTW ENG METH, V19, DOI 10.1145-1571629.1571631; Masri W, 2008, COMPUT SECUR, V27, P176, DOI 10.1016-j.cose.2008.06.002; Meinel Christoph, 1998, ALGORITHMS DATA STRU; Newsome J., 2005, P NETW DISTR SYST SE; PODGURSKI A, 1989, THESIS U MASS; PODGURSKI A, 1990, IEEE T SOFTWARE ENG, V16, P965, DOI 10.1109-32.58784; Rothermel G, 2001, IEEE T SOFTWARE ENG, V27, P929, DOI 10.1109-32.962562; Sinha S, 2001, ACM T SOFTW ENG METH, V10, P209, DOI 10.1145-367008.367022; STEVEN J, 2000, P 2000 INT S SOFTW T; ZHANG X, 2004, INT C SOFTW ENG ED U; Zhang X., 2003, IEEE ACM INT C SOFTW, P319; ZIMMERMANN J, 2003, 8 EUR S RES COMP SEC; ZIMMERMANN J, 2003, 19 COMP SEC APPL C L65
Coverage specification for test case intent preservation in regression suites
No full textRegression testing ensures that previous faults do not recur. When a fault is reported and fixed, the testing team augments the test suite with a new test case that exercises the fault in the original program. Typically the new test case covers patterns of program elements associated with the fault. However, this test might become obsolete (i.e., does not cover the targeted patterns anymore) when other code modifications are made. Nevertheless, current coverage metrics might still report acceptable values thus misleading the testing team. In this paper, we present a coverage specification language and a methodology to preserve the intent of test cases in a regression test suite. We implemented our methodology for C programs and for def-use program elements. With our method, a) a coverage specification language enables testers to specify def-use pairs and associate them with tests, b) the def-use pairs' specifications recognize the pairs across subsequent versions of the program, and c) the tool computes run time assembly level addresses for def-use pairs and guarantees intent preservation. Preliminary results show that our method works for program changes involving insertions and deletions of several lines of code. © 2013 IEEE.Abou-Assi R., 2011, 1 INT WORKSH TEST DE; Ammann P., 2008, INTRO SOFTWARE TESTI; Ammann P, 2003, ISSRE 2003: 14TH INTERNATIONAL SYMPOSIUM ON SOFTWARE RELIABILITY ENGINEERING, PROCEEDINGS, P99; Elbaum S, 2002, IEEE T SOFTWARE ENG, V28, P159, DOI 10.1109-32.988497; Graves TL, 2001, ACM T SOFTW ENG METH, V10, P184, DOI 10.1145-367008.367020; Gupta Neelam, 2000, AUTOMAT SOFTW ENG, P219; HARROLD MJ, 1994, ACM T PROGR LANG SYS, V16, P175, DOI 10.1145-174662.174663; Jones JA, 2003, IEEE T SOFTWARE ENG, V29, P195, DOI 10.1109-TSE.2003.1183927; Masri W., 2009, 7 INT WORKSH DYN AN; Masri W, 2009, INFORM SOFTWARE TECH, V51, P385, DOI 10.1016-j.infsof.2008.05.008; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; Masri W., 2008, EMPIRICAL SOFTWARE E, V13, P369; Masri W., 2009, INT WORKSH DEF LARG; Masri W, 2008, COMPUT SECUR, V27, P176, DOI 10.1016-j.cose.2008.06.002; Masri W, 2011, J SYST SOFTWARE, V84, P1171, DOI 10.1016-j.jss.2011.02.007; Parr T., ANTLR DOCUMENTATION; Reps T., 1997, 5 ACM SIGSOFT S FDN; Valgrind Developers Valgrind, VALGR DEV10
Does principal component analysis improve cluster-based analysis?
No full textResearchers in the dynamic program analysis field have extensively used cluster analysis to address various problems. Typically, the clustering techniques are applied onto execution profiles having high dimensionality (i.e., involving a large number of profiling elements), sometimes in the order of thousands or even hundreds of thousands. Our concern is that the high number of profiling elements might diminish the effectiveness of the clustering process, which led us to explore the use of dimensionality reduction techniques as a preprocessing step to clustering. Specifically, in this work, we used PCA (Principal Component Analysis) as a dimensionality reduction technique and investigated its impact on two cluster-based analysis techniques, one aiming at identifying coincidentally correct tests, and the other at test suite minimization. In other words, we tried to assess whether PCA improves cluster-based analysis. Our experimental results showed that the impact was positive on the first technique, but inconclusive on the second, which calls for further investigation in the future. © 2013 IEEE.Abou-Assi R., 2011, 1 INT WORKSH TEST DE; Ammann P., 2008, INTRO SOFTWARE TESTI; CATTELL RB, 1966, MULTIVAR BEHAV RES, V1, P245, DOI 10.1207-s15327906mbr0102_10; DICKINSON W, 2001, ICSE 2001, P339; Fodor I.K., 2002, SURVEY DIMENSION RED; Hatcher L, 1994, STEP BY STEP APPROAC; Hierons RM, 2006, ACM T SOFTW ENG METH, V15, P227, DOI 10.1145-1151695.1151696; Jones J., 2001, ICSE, P467; KAISER HF, 1960, EDUC PSYCHOL MEAS, V20, P141, DOI 10.1177-001316446002000116; LIBLIT B, 2003, P ACM SIGPLAN C PROG, V38, P141; Masri W., 2009, 7 INT WORKSH DYN AN; Masri W, 2008, EMPIR SOFTW ENG, V13, P369, DOI 10.1007-s10664-008-9071-y; Masri W, 2009, INFORM SOFTWARE TECH, V51, P385, DOI 10.1016-j.infsof.2008.05.008; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; Masri W, 2010, SOFTW TEST VERIF REL, V20, P121, DOI 10.1002-stvr.409; Masri W., 2009, INT WORKSH DEF LARG; Masri W., 2010, 3 INT C SOFTW TEST V; Masri W., 2012, REGR ICST 2012 MONTR; Masri W, 2011, J SYST SOFTWARE, V84, P1171, DOI 10.1016-j.jss.2011.02.007; Masri W., 2008, COMPUTERS SECURITY, V27; Reps T., 1997, 5 ACM SIGSOFT S FDN; Shlens Jonathon, 2009, TUTORIAL PRINCIPAL C; Smith L. I., 2002, TUTORIAL PRINCIPAL C; VOAS JM, 1992, IEEE T SOFTWARE ENG, V18, P717, DOI 10.1109-32.153381; Wang XM, 2009, PROC INT CONF SOFTW, P450
Application-based anomaly intrusion detection with dynamic information flow analysis
No full textThis paper presents a new approach to detecting software security failures, whose primary goal is facilitating identification and repair of security vulnerabilities rather than permitting online response to attacks. The approach is based on online capture of executions and offline execution replay, profiling, and analysis. It employs fine-grained dynamic information flow analysis in conjunction with anomaly detection. This approach, which we call information flow anomaly detection, is capable of detecting a variety of security failures, including both ones that involve violations of confidentiality or integrity requirements and ones that do not. A prototype tool called DynFlow implementing the approach has been developed for use with Java byte code programs. To illustrate the potential of the approach, it is applied to detect security failures of four open source systems. Also, its effectiveness is compared to the effectiveness of an approach to anomaly detection that is based on analyzing method call stacks. © 2008 Elsevier Ltd. All rights reserved.Axelsson S., 2000, ACM Transactions on Information and Systems Security, V3, DOI 10.1145-357830.357849; Axelsson S., 2000, 9915 CHALM U DEP COM; *BCEL, 2003, AP JAK PROJ AP SOFTW; CHATURVEDI A, 2005, SECLAB0503 STON BROO; DENNING DE, 1977, COMMUN ACM, V20, P504, DOI 10.1145-359636.359712; DENNING DE, 1987, IEEE T SOFTWARE ENG, V13, P222, DOI 10.1109-TSE.1987.232894; DICKINSON W, 2001, 23 INT C SOFTW ENG T, P339; DICKINSON W, 2001, 10 EUR SOFTW ENG C 9, P246; FENG H, 2003, IEEE S SEC PRIV OAKL; FENTON JS, 1974, COMPUT J, V17, P143, DOI 10.1093-comjnl-17.2.143; Forrest S., 1996, IEEE S SEC PRIV, P120; HALDAR V, 2005, 0502 U CAL DEP INF C; Hofmeyr S. A., 1998, Journal of Computer Security, V6; Jain A. K., 1988, ALGORITHMS CLUSTERIN; Leon D., 2005, 27 INT C SOFTW ENG S; Liepins G., 1989, 12 NAT COMP SEC C BA, P495; MASRI W, 2005, 2005 WORKSH SOFTW EN; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; MASRI W, 2004, 15 IEEE INT S SOFTW; MASRI W, 2006, 17 IEEE INT S SOFTW; MASRI WB, 2004, THESIS; MCCAMANT S, 2007, ACM SIGPLAN WORKSH P; MCCAMANT S, 2006, MITCSAILTR2006076; MCMASTER S, 2005, 21 INT C SOFTW MAINT; NEWSOME J, 2005, 12 NETW DISTR SYST S; ORSO A, 2005, 2005 WORKSH DYN AN S; *PERL ORG, PERL DIR; Steven S., 2000, 2000 INT S SOFTW TES, P158; SUH GE, 2004, 11 INT C ARCH SUPP P; TALLAM S, 2007, ACM T ARCHITECTURE C, V4; TAN K, 2002, 5 INT S REC ADV INTR; VACHHARAJANI N, 2004, P 37 INT S MICR MICR; Vogt P., 2007, 14 ANN NETW DISTR SY; Wagner D., 2002, P 9 ACM C COMP COMM, P255; Xu W, 2005, SECLAB0505 STON BROO; Zhang XY, 2005, ACM T PROGR LANG SYS, V27, P631, DOI 10.1145-1075382.1075384; ZIMMERMANN J, 2003, LECT NOTES COMPUTER, V2808; ZIMMERMANN J, 2003, 19 COMP SEC APPL C L199
An empirical study of test case filtering techniques based on exercising information flows
No full textSome software defects trigger failures only when certain local or nonlocal program interactions occur. Such interactions are modeled by the closely related concepts of information flows, program dependences, and program slices. The latter concepts underlie a 78variety of proposed test data adequacy criteria, and they form a potentially important basis for filtering existing test cases. We report the results of an empirical study of several test case filtering techniques that are based on exercising information flows. Both coverage-based and profile-distribution-based filtering techniques are considered. They are compared to filtering techniques based on exercising simpler program elements, such as basic blocks, branches, function calls, and call pairs, with respect to their effectiveness for revealing defects. © 2007 IEEE.Agrawal H., 1993, Proceedings. Conference on Software Maintenance 1993. CSM-93 (Cat. No.93CH3360-5), DOI 10.1109-ICSM.1993.366927; Bates S., 1993, P 20 ACM S PRINC PRO, P384, DOI 10.1145-158511.158694; *BCEL, 2005, AP JAK PROJ; CLARKE LA, 1989, IEEE T SOFTWARE ENG, V15, P1381; DENNING DE, 1977, COMMUN ACM, V20, P504, DOI 10.1145-359636.359712; Dickinson W, 2001, PROC INT CONF SOFTW, P339, DOI 10.1109-ICSE.2001.919107; Dickinson W., 2001, P JOINT 8 EUR SOFTW, P246; Elbaum S, 2002, IEEE T SOFTWARE ENG, V28, P159, DOI 10.1109-32.988497; FERRANTE J, 1987, ACM T PROGR LANG SYS, V9, P319, DOI 10.1145-24039.24041; Frank MP, 1998, NANOTECHNOLOGY, V9, P162, DOI 10.1088-0957-4484-9-3-005; Frankl P. G., 2000, P ACM INT S SOFTW TE, P124, DOI 10.1145-347324.348926; Graves TL, 2001, ACM T SOFTW ENG METH, V10, P184, DOI 10.1145-367008.367020; Gupta KC, 1996, INT J MICROWAVE MILL, V6, P83; HAROLD MJ, 2000, J SOFTWARE TESTING V, V10, P171; Hochbaum D.S, 1997, APPROXIMATION ALGORI; KIM JM, 2002, P 24 INT C SOFTW ENG, P119; KOREL B, 1987, INFORM PROCESS LETT, V24, P103, DOI 10.1016-0020-0190(87)90102-5; KOREL B, 1994, P INT S SOFTW TEST A, P666; KOREL B, 1988, INFORM PROCESS LETT, V29, P155, DOI 10.1016-0020-0190(88)90054-3; LASKI JW, 1983, IEEE T SOFTWARE ENG, V9, P347, DOI 10.1109-TSE.1983.236871; LEON D, 2003, P INT S SOFTW REL EN, P442; Leon D, 2005, PROC INT CONF SOFTW, P412; Leon D., 2000, Proceedings of the 2000 International Conference on Software Engineering. ICSE 2000 the New Millennium, DOI 10.1109-ICSE.2000.870403; MASRI W, 2006, P 4 INT WORKSH DYN A; Masri W., 2005, P WORKSH SOFTW ENG S, P1, DOI 10.1145-1083200.1083216; MASRI W, 2006, P 17 IEEE INT S SOFT; Masri W., 2004, P 15 INT S SOFTW REL, P198; *MIT I NATL RECH I, 1998, JTIDY WORLD WID WEB; MORELL LJ, 1990, IEEE T SOFTWARE ENG, V16, P844, DOI 10.1109-32.57623; NTAFOS SC, 1984, IEEE T SOFTWARE ENG, V10, P795; Podgurski A, 2003, PROC INT CONF SOFTW, P465, DOI 10.1109-ICSE.2003.1201224; PODGURSKI A, 1990, IEEE T SOFTWARE ENG, V16, P965, DOI 10.1109-32.58784; RAPPS S, 1985, IEEE T SOFTWARE ENG, V11, P367, DOI 10.1109-TSE.1985.232226; Rothermel G, 2001, IEEE T SOFTWARE ENG, V27, P929, DOI 10.1109-32.962562; Rothermel G., 1994, P 1994 INT S SOFTW T, P169; Rothermel G., 1993, Proceedings. Conference on Software Maintenance 1993. CSM-93 (Cat. No.93CH3360-5), DOI 10.1109-ICSM.1993.366926; Rothermel G, 1998, PROC IEEE INT CONF S, P34, DOI 10.1109-ICSM.1998.738487; SINHA S, 2000, ACM T SOFTW ENG METH, P209; *SIR, 2006, SOFTW ART INFR REP; *SUN MICR, JAV LANG SPEC; Thompson Margaret C., 1993, P ACM INT S SOFTW TE, P182, DOI 10.1145-154183.154270; WEISER M, 1984, IEEE T SOFTWARE ENG, V10, P352; Wong WE, 1997, P INT COMP SOFTW APP, P522, DOI 10.1109-CMPSAC.1997.625062; 2005, XERCES APACHE XML PR39262
Leveraging strength-based dynamic information flow analysis to enhance data value prediction
No full textValue prediction is a technique to increase parallelism by attempting to overcome serialization constraints caused by true data dependences. By predicting the outcome of an instruction before it executes, value prediction allows data dependent instructions to issue and execute speculatively, hence increasing parallelism when the prediction is correct. In case of a misprediction, the execution is redone with the corrected value. If the benefit from increased parallelism outweighs the misprediction recovery penalty, overall performance could be improved. Enhancing performance with value prediction therefore requires highly accurate prediction methods. Most existing general value prediction techniques are local, that is, future outputs of an instruction are predicted based on outputs from previous executions of the same instruction. In this article, we investigate leveraging strength-based dynamic information flow analysis to enhance data value prediction. We use dynamic information flow analysis (DIFA) to determine when a specific value predictor can perform well and even outperform other predictors. We apply information theory to mathematically prove the validity and benefits of correlating value predictors. We also introduce the concept of the linear value predictors, a new technique that predicts a new value from another one using a linear relation. We finally present a variant of stride predictor that we call update stride. We then conduct an empirical analysis using Pin, a dynamic binary instrumentation tool, and DynFlow, a dynamic information flow analysis tool, that we apply to programs from the SPECjvm2008 and Siemens benchmarks. Our empirical measurements support our mathematical theory and allow us to make important observations on the relation between predictability of data values and information flow. Our analysis and empirical results show that the values of a set of selected variables can be predicted with a very high accuracy, up to 100percent. Such prediction is based on the previous history and-or the values of one or more other source variables that have strong information flow into the predicted variable. Using our selection criteria, we show that a DIFA-directed predictor outperforms hardware value prediction for all subject programs, and sometimes by a significant margin. This was observed even when using an ideal tagged hardware value prediction table that does not suffer from aliasing or capacity misses. © 2012 ACM 1544-3566-2012-03-ART1 $10.00.Ahuja P, 1998, P 12 INT C SUP JUL, P101, DOI 10.1145-277830.277854; AKKARY H., 2003, P 17 ANN INT C SUP, P12; AKKARY H, 1998, P ANN ACM IEEE INT S; AKKARY H., 2008, P INT FOR NEXT GEN M; Allison P.D., 1998, MULTIPLE REGRESSION; AL-ZAWAWI A. S., 2007, P 34 ANN INT S COMP; AUSTIN T. M, 1992, P 19 INT S COMP ARCH, P342, DOI 10.1145-139669.140395; Bishop M., 2002, COMPUTER SECURITY AR; Burtscher M, 2002, IEEE T COMPUT, V51, P759, DOI 10.1109-TC.2002.1017696; Burtscher M., 1999, P INT C PAR ARCH COM, P66; Butler M., 1991, P 18 INT S COMP ARCH, P276, DOI 10.1145-115952.115980; CALDER B., 1999, P 26 ANN INT S COMP; CHRYSOS G. Z, 1998, P 25 ANN INT S COMP; Cover TM, 1991, ELEMENTS INFORM THEO; Denning D. E., 1982, CRYPTOGRAPHY DATA SE; Do HS, 2005, EMPIR SOFTW ENG, V10, P405, DOI 10.1007-s10664-005-3861-2; EICKEMEYER RJ, 1993, IBM J RES DEV, V37, P547; Ellis JR, 1986, BULLDOG COMPILER VLI; Fano R. M., 1961, TRANSMISSION INFORM; FRANKLIN M, 1993, THESIS U WISCONSIN; Gabbay F, 1997, INT SYMP MICROARCH, P270; GANDHI A., 2004, P 10 INT S HIGH PERF; Ganusov I., 2006, ACM Transactions on Architecture and Code Optimization, V3, DOI 10.1145-1187976.1187979; GHANDOUR W. J, 2009, CONT ENG SCI, V2, P517; Ghandour WJ, 2010, PACT 2010: PROCEEDINGS OF THE NINETEENTH INTERNATIONAL CONFERENCE ON PARALLEL ARCHITECTURES AND COMPILATION TECHNIQUES, P431, DOI 10.1145-1854273.1854327; Goeman B., 2001, Proceedings HPCA Seventh International Symposium on High-Performance Computer Architecture, DOI 10.1109-HPCA.2001.903264; Hu Shiwen, 2003, J INSTRUCTION LEVEL, V5, P1; HWU W. W, 1995, P IEEE 83, V83, P12; INTEL, 2006, 245319005 INTEL; Kachigan S. K., 1986, STAT ANAL INTERDISCI; Kirman N, 2005, INT S HIGH PERF COMP, P16, DOI 10.1109-HPCA.2005.9; KRUS D. J, 2006, VISUAL STAT; Kwak JW, 2007, MICROPROCESS MICROSY, V31, P63, DOI 10.1016-j.micpro.2006.08.002; LAM M. S, 1992, P 19 ANN INT S COMP, P46, DOI 10.1145-139669.139702; Lipasti M. H., 1996, P 7 INT C ARCH SUPP, P138, DOI 10.1145-237090.237173; Lipasti MH, 1996, PROCEEDINGS OF THE 29TH ANNUAL IEEE-ACM INTERNATIONAL SYMPOSIUM ON MICROARCHITECTURE - MICRO-29, P226, DOI 10.1109-MICRO.1996.566464; Luk C.-K., 2005, P ACM SIGPLAN C PROG; MARCUELLO P., 1999, P 32 INT S MICR; Marcuello P, 2004, IEEE T COMPUT, V53, P114, DOI 10.1109-TC.2004.1261823; Masri W, 2009, INFORM SOFTWARE TECH, V51, P385, DOI 10.1016-j.infsof.2008.05.008; MASRI W., 2004, P 15 IEEE INT S SOFT; Masri W, 2007, IEEE T SOFTWARE ENG, V33, P454, DOI 10.1109-TSE.2007.1020; Masri W., 2009, ACM T SOFTW ENG METH, V19, P2; Masri W., 2006, P INT WORKSH DYN AN, P73, DOI 10.1145-1138912.1138927; MOHAN W, 1992, P 5 INT C ARCH SUPP, P76; MONTOYE RK, 1990, IBM J RES DEV, V34, P59; Moshovos A, 2002, IEEE T COMPUT, V51, P313, DOI 10.1109-12.990129; MOSHOVOS A., 1997, P 24 ANN ACM IEEE C; MOSHOVOS A. I, 1998, THESIS U WISCONSIN M; NAKRA T., 1999, P 5 INT S HIGH PERF; OPLINGER J., 1999, P 8 INT C PAR ARCH C; Papworth DB, 1996, IEEE MICRO, V16, P8, DOI 10.1109-40.491458; PICKETT C. J. F, 2004, SABLETR20046 MCGILL; PICKETT C. J. F, 2004, P 2 VAL PRED VAL BAS; Rychlik B., 1998, Proceedings. 1998 International Conference on Parallel Architectures and Compilation Techniques (Cat. No.98EX192), DOI 10.1109-PACT.1998.727186; SAM N. B, 2005, P 4 ANN WORKSH DUPL, P16; Sazeides Y., 1997, P 30 INT S MICR; SAZEIDES Y, 2002, P 8 INT S HIGH PERF; SAZEIDES Y., 1996, P 29 ANN ACM IEEE IN; SAZEIDES Y, 1997, ECET978 U WISC MAD; Siegel S., 1956, NONPARAMETRIC STAT B; SINGER J, 2006, P 4 INT WORKSH QUANT, P137; Smith A, 2006, INT SYMP MICROARCH, P89; Smith James E., 1981, P 8 ANN INT S COMP A, P135; Smith JE, 1995, P IEEE, V83, P1609, DOI 10.1109-5.476078; SODANI A, 1997, P 24 ANN INT S COMP; Sodani A., 1998, Proceedings. 31st Annual ACM-IEEE International Symposium on Microarchitecture, DOI 10.1109-MICRO.1998.742782; STEFFAN J., 1999, P 8 INT S HIGH PERF; Thomas R., 2001, Proceedings 2001 International Conference on Parallel Architectures and Compilation Techniques, DOI 10.1109-PACT.2001.953292; Thomas R, 2003, CONF PROC INT SYMP C, P314, DOI 10.1109-ISCA.2003.1207010; Tuck N., 2005, P 11 INT S HIGH PERF; TULLSEN D, 1999, P 26 INT S COMP ARCH; Vandierendonck H, 2010, PR IEEE COMP DESIGN, P364, DOI 10.1109-ICCD.2010.5647699; Wang K., 1997, Proceedings. Thirtieth Annual IEEE-ACM International Symposium on Microarchitecture (Cat. No.97TB100184), DOI 10.1109-MICRO.1997.645819; WARTER N., 1993, P 26 ANN HAW INT C S, P497; YOURST MT, 2007, P INT S PERF AN SYST, P23; Zhao Q, 2004, IEEE T COMPUT, V53, P929, DOI 10.1109-TC.2004.49; Zhou HY, 2003, CONF PROC INT SYMP C, P3240
- …
