skip to main content
10.5555/1895949.1895977guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

Automated logic synthesis of random pattern testable circuits

Published: 02 October 1994 Publication History

Abstract

Previous approaches to designing random pattem testable circuits use post-synthesis test point insertion to eliminate random pattern resistant (r.p.r.) faults. The approach taken in this paper is to consider random pattern testability during logic synthesis. An automated logic synthesis procedure is presented which takes as an input a two-level representation of a circuit and a constraint on the minimum fault detection probability (threshold below which faults are considered r.p.r.) and generates a multilevel implementation that satisfies the constraint while minimizing the literal count. The procedure identifies r.p.r. faults and attempts to "eliminate" them through algebraic factoring. If that is not possible, then test points are inserted during the synthesis process in a way that minimizes the number of test points that are required. Results are shown for benchmark circuits which indicate that the proposed procedure can generally reduce the random pattern test length by at least an order of magnitude with only a small area overhead.

References

[1]
Abadi, M. 1998. Protection in programming-language translations. In Proceedings of the 25th International Colloquium on Automata, Languages and Programming. Springer-Verlag, Berlin, 868--883.
[2]
Agat, J. 2000. Transforming out timing leaks. In Proceedings of the Symposium on Principles of Programming Languages. ACM, New York, 40--53.
[3]
Almeida Matos, A. 2006. Typing secure information flow: Declassification and mobility. Ph.D. thesis, Ecole Nationale Supérieure des Mines de Paris.
[4]
Banerjee, A. and Naumann, D. A. 2005. Stack-based access control and secure information flow. J. Funct. Program. 15, 2, 131--177.
[5]
Barnes, J. and Barnes, J. 2003. High Integrity Software: The SPARK Approach to Safety and Security. Addison-Wesley Longman, Boston.
[6]
Barthe, G., Pichardie, D., and Rezk, T. 2007. A certified lightweight non-interference java bytecode verifier. In Proceedings of the European Symposium on Programming. Springer, Berlin.
[7]
Barthe, G. and Rezk, T. 2005. Non-interference for a JVM-like language. In Proceedings of the International Workshop on Types of Languages Design and Implementation. ACM, New York, 103--112.
[8]
Barthe, G., Rezk, T., and Basu, A. 2007. Security types preserving compilation. J. Comput. Lang. Syst. Struct.
[9]
Barthe, G., Rezk, T., and Naumann, D. 2006. Deriving an information flow checker and certifying compiler for java. In Proceedings of the Symposium on Security and Privacy. IEEE, Los Alamitos, CA, 230--242.
[10]
Barthe, G., Rezk, T., Russo, A., and Sabelfeld, A. 2007. Security of multithreaded programs by compilation. In Proceedings of the European Symposium on Research in Computer Security. Springer-Verlag, Berlin, 2--18.
[11]
Barthe, G., Rezk, T., Russo, A., and Sabelfeld, A. 2009. Security of multithreaded programs by compilation. Full version. Tech. rep. http://www.cse.chalmers.se/~russo/tissecfull.pdf.
[12]
Boudol, G. and Castellani, I. 2002. Noninterference for concurrent programs and thread systems. Theor. Comput. Sci. 281, 1, 109--130.
[13]
Chapman, R. and Hilton, A. 2004. Enforcing security and safety models with an information flow analysis tool. ACM SIGAda Ada Lett. 24, 4, 39--46.
[14]
Denning, D. E. and Denning, P. J. 1977. Certification of programs for secure information flow. Comm. ACM 20, 7, 504--513.
[15]
Focardi, R. and Gorrieri, R. 2001. Classification of security properties (Part I: Information flow). In Foundations of Security Analysis and Design, R. Focardi and R. Gorrieri, Eds. Springer-Verlag, Berlin, 331--396.
[16]
Genaim, S. and Spoto, F. 2005. Information flow analysis for Javab. In Proceedings of the International Conference on Verification, Model Checking, and Abstract Interpretation. Springer-Verlag, Berlin, 346--362.
[17]
Goguen, J. A. and Meseguer, J. 1982. Security policies and security models. In Proceedings of the Symposium on Security and Privacy. IEEE, Los Alamitos, CA, 11--20.
[18]
Hedin, D. and Sands, D. 2006. Noninterference in the presence of non-opaque pointers. In Proceedings of the 19th Computer Security Foundations Workshop. IEEE, Los Alamitos, CA, 255--269.
[19]
Honda, K., Vasconcelos, V., and Yoshida, N. 2000. Secure information flow as typed process behaviour. In Proceedings of the European Symposium on Programming. Springer-Verlag, Berlin, 180--199.
[20]
Honda, K. and Yoshida, N. 2002. A uniform type structure for secure information flow. In Proceedings of the Symposium on Principles of Programming Languages. ACM, New York, 81--92.
[21]
Huisman, M., Worah, P., and Sunesen, K. 2006. A temporal logic characterisation of observational determinism. In Proceedings of the Computer Security Foundations Symposium. IEEE, Los Alamitos, CA.
[22]
Knudsen, J. 2002. Networking, user experience, and threads. Sun Technical Articles and Tips http://developers.sun.com/techtopics/mobility/midp/articles/threading/.
[23]
Köpf, B. and Mantel, H. 2006. Eliminating implicit information leaks by transformational typing and unification. In Proceedings of the 3rd International Workshop on Formal Aspects in Security and Trust. Springer-Verlag, Berlin, 47--62.
[24]
Mahmoud, Q. H. 2004. Preventing screen lockups of blocking operations. Sun Technical Articles and Tips. http://developers.sun.com/techtopics/mobility/midp/ttips/screenlock/.
[25]
Medel, R., Compagnoni, A., and Bonelli, E. 2005. A typed assembly language for noninterference. In Proceedings of the Italian Conference on Theoretical Computer Science. Springer-Verlag, Berlin, 360--374.
[26]
Morrisett, G., Walker, D., Crary, K., and Glew, N. 1999. From System F to typed assembly language. ACM Trans. Program. Lang. Syst. 21, 3, 528--569.
[27]
Myers, A. C. 1999. JFlow: Practical mostly-static information flow control. In Proceedings of the Symposium on Principles of Programming Languages. ACM, New York, 228--241.
[28]
Myers, A. C., Zheng, L., Zdancewic, S., Chong, S., and Nystrom, N. 2001. JIF: Java information flow. Software release. http://www.cs.cornell.edu/jif.
[29]
Necula, G. C. 1997. Proof-carrying code. In Proceedings of the Symposium on Principles of Programming Languages. ACM, New York, 106--119.
[30]
Pottier, F. 2002. A simple view of type-secure information flow in the pi-calculus. In Proceedings of the IEEE Computer Security Foundations Symposium. IEEE, Los Alamitos, CA, 320--330.
[31]
Pottier, F. and Simonet, V. 2003. Information flow inference for ML. ACM Trans. Program. Lang. Syst. 25, 1, 117--158.
[32]
Rezk, T. 2006. Verification of confidentiality policies for mobile code. Ph.D. thesis, Université de Nice Sophia-Antipolis.
[33]
Russo, A., Hughes, J., Naumann, D., and Sabelfeld, A. 2007. Closing internal timing channels by transformation. In Proceedings of the Asian Computing Science Conference. Springer-Verlag, Berlin.
[34]
Russo, A. and Sabelfeld, A. 2006a. Securing interaction between threads and the scheduler. In Proceedings of the Computer Security Foundations Symposium. IEEE, Los Alamitos, CA, 177--189.
[35]
Russo, A. and Sabelfeld, A. 2006b. Security for multithreaded programs under cooperative scheduling. In Proceedings of the Andrei Ershov International Conference on Perspectives of System Informatics. Springer-Verlag, Berlin.
[36]
Ryan, P. 2001. Mathematical models of computer security—tutorial lectures. In Foundations of Security Analysis and Design, R. Focardi and R. Gorrieri, Eds. Springer-Verlag, Berlin, 1--62.
[37]
Sabelfeld, A. 2001. The impact of synchronisation on secure information flow in concurrent programs. In Proceedings of the Andrei Ershov International Conference on Perspectives of System Informatics. Springer-Verlag, Berlin, 225--239.
[38]
Sabelfeld, A. and Mantel, H. 2002. Static confidentiality enforcement for distributed programs. In Proceedings of the Symposium on Static Analysis. Springer-Verlag, Berlin, 376--394.
[39]
Sabelfeld, A. and Myers, A. C. 2003. Language-based information-flow security. IEEE J. Sel. Areas Comm. 21, 1, 5--19.
[40]
Sabelfeld, A. and Sands, D. 2000. Probabilistic noninterference for multi-threaded programs. In Proceedings of the Computer Security Foundations Symposium. IEEE, Los Alamitos, CA, 200--214.
[41]
Simonet, V. 2003. The Flow Caml system. Software release. http://cristal.inria.fr/_simonet/soft/flowcaml/.
[42]
Smith, G. 2001. A new type system for secure information flow. In Proceedings of the Computer Security Foundations Symposium. IEEE, Los Alamitos, CA, 115--125.
[43]
Smith, G. 2003. Probabilistic noninterference through weak probabilistic bisimulation. In Proceedings of the Computer Security Foundations Symposium. IEEE, Los Alamitos, CA, 3--13.
[44]
Smith, G. and Volpano, D. 1998. Secure information flow in a multithreaded imperative language. In Proceedings of the Symposium on Principles of Programming Languages. ACM, New York, 355--364.
[45]
Terauchi, T. 2008. A type system for observational determinism. In Proceedings of the 21st Computer Security Foundations Symposium. IEEE, Los Alamitos, CA.
[46]
Tsai, T. C., Russo, A., and Hughes, J. 2007. A library for secure multithreaded information flow in Haskell. In Proceedings of the 20th Computer Security Foundations Symposium. IEEE, Los Alamitos, CA.
[47]
van der Meyden, R. and Zhang, C. 2008. Information flow in systems with schedulers. In Proceedings of the Computer Security Foundation Symposium. IEEE, Los Alamitos, CA.
[48]
Volpano, D. and Smith, G. 1999. Probabilistic noninterference in a concurrent language. J. Comput. Secur. 7, 2--3, 231--253.
[49]
Volpano, D., Smith, G., and Irvine, C. 1996. A sound type system for secure flow analysis. J. Comput. Secur. 4, 3, 167--187.
[50]
Zanardini, D. 2006. Abstract noninterference in a fragment of java bytecode. In Proceedings of the Symposium on Applied Computing. ACM, New York, 1822--1826.
[51]
Zdancewic, S. and Myers, A. C. 2003. Observational determinism for concurrent program security. In Proceedings of the Computer Security Foundations Symposium. IEEE, Los Alamitos, CA, 29--43.
  1. Automated logic synthesis of random pattern testable circuits

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image Guide Proceedings
    ITC'94: Proceedings of the 1994 international conference on Test
    October 1994
    1024 pages
    ISBN:0780321022

    Publisher

    IEEE Computer Society

    United States

    Publication History

    Published: 02 October 1994

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 157
      Total Downloads
    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    View Options

    View options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media