Information hiding for trusted system design

ABSTRACT

For a computing system to be trusted, it is equally important to verify that the system performs no more and no less functionalities than desired. Traditional testing and verification methods are developed to validate whether the system meets all the requirements. They cannot detect the existence or show the non-existence of the unknown undesired functionalities. In this paper, we propose a novel approach that converts this problem to a less challenging design quality measuring problem. Our approach is based on information hiding and constraint manipulation of the original system design specification. We lay out the basic requirements for our approach and demonstrate it through the popular graph coloring problem. Results show that information can be embedded into the original graph without significant impact to the solution quality. However, when the same information is added to the graph modified based on our approach, there will be noticeable drop in the solution quality.

REFERENCES

• 1: Report of the Defense Science Board Task Force on High Performance Microchip Supply, February 2005.
• 2: B. S. Cohen. "On Integrated Circuits Supply Chain Issues in a Global Commercial Market --Defense Security and Access Concerns", March 2007.
• 3: C. E. Irvine and K. Levitt. "Trusted Hardware: Can It Be Trustworthy?", ACM/IEEE Design Automation Conference, pp. 1--4, June 2007.
• 4: S. Trimberger. "Trusted Design in FPGAs", ACM/IEEE Design Automation Conference, pp. 5--8, June 2007.
• 5: G. E. Suh and S. Devadas. "Physical Unclonable Functions for Device Authentication and Secret Key Generation", ACM/IEEE Design Automation Conference, pp. 9--12, June 2007.
• 6: D. Kirovski and M. Potkonjak. "Efficient Coloring of a Large Spectrum of Graphs", ACM/IEEE Design Automation Conference Proceedings, pp. 427--432, June 1998.
• 7: G. Qu and M. Potkonjak, Hiding Signatures in Graph Coloring Solutions", Information Hiding Workshop, pp. 391--408, 1999.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.m MISCELLANEOUS
      Subjects: Design management

General Terms:
Algorithms, Legal Aspects, Measurement, Security, Verification

Keywords:
VLSI design intellectual property, constraint manipulation, graph coloring, information hiding, trusted IC