Measuring the strength of information flows in programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Measuring the strength of information flows in programs

Full text

Pdf (2.45 MB)

Source

ACM Transactions on Software Engineering and Methodology (TOSEM) archive
Volume 19 , Issue 2 (October 2009) table of contents

Article No. 5

Year of Publication: 2009

ISSN:1049-331X

Authors

Wes Masri	American University of Beirut, Beirut, Lebanon
Andy Podgurski	Case Western Reserve University, Cleveland, OH

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 137, Downloads (12 Months): 137, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1571629.1571631 What is a DOI?

ABSTRACT

Dynamic 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Agrawal, H. and Horgan, J. 1990. Dynamic program slicing. SIGPLAN Not. 25, 6 (June), 246--256.
	2	Apiwattanapong, T., Orso A., and Harrold, M. J. 2005. Efficient and precise dynamic impact analysis using ExecuteAfter sequences. In Proceedings of the International Conference on Software Engineering (St. Louis, MO, May).
	3	Binkley, D. and Harman, M. 2004. Analysis and visualization of predicate dependence on formal parameters and global variables. IEEE Trans. Softw. Eng. 30, 11, 715--735.
	4	Bishop, M. 2002. Computer Security: Art and Science. Addison-Wesley, Reading, MA.
	5	Box, G. E. P., Hunter, J. S., and Hunter, W. G. 2005. Statistics for Experimenters: Design, Innovation, and Discovery, 2nd ed. Wiley, New York, NY.
	6	Clark, D., Hunt S., and Malacaria, P. 2001. Quantitative analysis of the leakage of confidential data. In Proceedings of Quantitative Aspects of Programming Languages (QAPL).
	7	Clark, D., Hunt S., and Malacaria, P. 2004. Quantified interference: Information theory and information flow. In Proceedings of the IFIP WG 1.7, ACM SIGPLAN, and GI FoMSESS Workshop on Issues in the Theory of Security (Barcelona, Spain, Apr.).
	8	Clause, J., Li, W., and Orso, A. 2007. Dytan: A generic dynamic taint analysis framework. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA).
	9	Cover, T. M. and Joy, T. A. 1991. Elements of Information Theory. Wiley, New York, NY.
	10	Dallmeier, V., Lindig, C., Wasylkowski, A., Zeller, A. 2006. Mining object behavior with ADABU. In Proceedings of the 4th International Workshop on Dynamic Analysis (WODA, Shanghai, China, May).
	11	Denning, D. E. 1976. A lattice model of secure information flow. Commun. ACM. 19, 5, 236--242.
	12	Denning, D. E. 1982. Cryptography and Data Security. Addison-Wesley, Reading, MA.
	13	Denning, D. E. and Denning, P. J. 1977. Certification of programs for secure information flow. Commun. ACM. 20, 7, 504--513.
	14	Do, H., Elbaum, S., and Rothermel, G. 2005. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Emp. Softw. Eng. Internat. J. 10, 4, 405--435.
	15	Fenton, J. S. 1974. Memoryless subsystems. Comput. J. 17, 2, 143--147.
	16	Ferrante, J., Ottenstein, K. J., and Warren, J. D. 1987. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9, 3 (July), 319--349.
	17	Kachigan, S. 1986. Statistical Analysis: An Interdisciplinary Introduction to Univariate & Multivariate Methods. Radius Press, New York, NY.
	18	Korel, B. and Yalamanchili, S. 1994. Forward computation of dynamic program slices. In Proceedings of the ISSTA, 66--79.
	19	Krus, D. J. 2006. Visual statistics: Chapter 14. Regression on Multiple Categories. visualstatistics.net.
	20	Lampson, B. W. 1973. A note on the confinement problem. Commun. ACM. 16, 10, 613--615.
	21	Law, J. and Rothermel, G. 2003. Whole program path-based dynamic impact analysis. In Proceedings of the International Conference on Software Engineering. 308--318.
	22	Lieberherr, K. J. 2004. Controlling the complexity of software designs. In Proceedings of the International Conference on Software Engineering (Edinburgh, Scotland). 2--11.
	23	Lowe, G. 2002. Quantifying information flow. In Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW), 18--31.
	24	Masri, W. 2004. Dynamic information flow analysis, slicing and profiling. Ph.D. dissertation. Case Western Reserve University, Cleveland, OH. wwwlib.umi.com/dissertations/fullcit/3146448.
	25	Masri, W. and Podgurski, A. 2005. Using dynamic information flow analysis to detect attacks against applications. In Proceedings of the Software Engineering for Secure Systems (SESS, St. Louis, MO, May).
	26	Masri, W. and Podgurski, A. 2006. An empirical study of the strength of information flows in programs. In Proceedings of the 4th International Workshop on Dynamic Analysis (WODA, Shanghai, China, May).
	27	Masri, W., Podgurski, A., and Leon, D. 2004. Detecting and debugging insecure information flows. In Proceedings of the 15th IEEE International Symposium on Software Reliability Engineering (ISSRE, St. Malo, France, Nov.).
	28	Masri, W., Podgurski, A., and Leon, D. 2007. An empirical study of test case filtering techniques based on exercising information flows. In Proceedings of the IEEE Trans. Softw. Eng. 33, 7, 454--477.
	29	McCamant, S. and Ernst, M. 2006. Quantitative information-flow tracking for C and related languages. MIT Computer Science and Artificial Intelligence Laboratory Tech. rep. MIT-CSAIL-TR-2006-076. MIT, Cambridge, MA.
	30	McCamant, S. and Ernst, M. 2007. A simulation-based proof technique for dynamic information flow. In Proceedings of the ACM SIGPLAN Workshop on Programming Languages and Analysis for Security (San Diego, CA, June).
	31	Newsome, J. and Song, D. 2005. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In Proceedings of the Network and Distributed System Security Symposium.
	32	NIST. 2001. Announcing the Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197, Nov. 26. National Institute of Science and Technology, Gaithersburg, MD. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.
	33	Pearl, J. 2000. Causality. Cambridge University Press, Cambridge, U.K.
	34	Podgurski, A. 1989. Significance of program dependences for software testing, debugging and maintenance. Ph.D. dissertation, Computer Science Department, University of Massachusetts, Amherst, MA.
	35	Podgurski, A. and Clarke, L. 1990. A formal model of program dependencies and its implications for software testing, debugging, and maintenance. IEEE Trans. Softw. Eng. 16, 9, 965--979.
	36	Sabelfeld, A. and Myers, A. C. 2003. Language-based information-flow security. IEEE J. Select. Areas Commun. 21, 1, 5--19.
	37	Siegel, S. 1956. Nonparametric Statistics For The Behavioral Sciences. McGraw-Hill, New York, NY.
	38	Sinha S., Harrold, M. J., and Rothermel, G. 2000. Interprocedural control dependence. ACM Trans. Softw. Eng. Methodol. 10, 1, 209--254.
	39	Spirtes, P., Glymour, C., and Scheines, R. 2000. Causality, Prediction, and Search, 2nd ed. MIT Press, Cambridge, MA.
	40	Steven, S., Chandra, P., Fleck, B., and Podgurski, A. 2000. jRapture: A capture/replay tool for observation-based testing. 2000. In Proceedings of the International Symposium on Software Testing and Analysis. (Portland, OR), 158--167.
	41	Tip, F. 1995. A survey of program slicing techniques. J. Program. Lang. 3, 3, 121--189.
	42	Visser, W., Havelund, K., Brat, G. P., Park, S., and Lerda, F. 2003. Model checking programs. Automat. Softw. Eng. 10, 2, 203--232.
	43	Voas, J. and Miller, K. 1993. Semantic metrics for software testability. J. Syst. Softw. 20, 3, 207--216.
	44	Woodward M. and Al-Khanjar, Z. 2000. Testability, fault size and the domain-to-range ratio: An eternal triangle. In Proceedings of the ISSTA. 168--172.
	45	Xie, T., Martin, E., and Yuan, H. 2006. Automatic extraction of abstract-object-state machines from unit-test executions. In Proceedings of the 28th International Conference on Software Engineering (ICSE). Research demonstrations.
	46	Zhang, X., Gupta, N., and Gupta, R. 2006a. Locating faults through automated predicate switching. In Proceedings of the International Conference on Software Engineering.
	47	Zhang, X., Gupta, N., and Gupta, R. 2006b. Pruning dynamic slices with confidence, In Proceedings of the PLDI.
	48	Zhang, X. and Gupta, R. 2004. Cost effective dynamic program slicing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (Washington, DC, June). 94--106.
	49	Zhang, X., He, H., Gupta, N., and Gupta, R. 2005. Experimental evaluation of using dynamic slices for fault location. In Proceedings of the AADEBUG.