Opaque constructs have developed into a commonly used primitive in obfuscation, watermarking, and tamper-proofing schemes. However, most prior work has based the resilience of these primitives on a poorly defined reduction to a known NP-complete problem. There has been little scrutiny of the adversarial model and little discussion of how to generate instances that are always hard. In this paper, we offer what we believe to be the first complete algorithm for generating resilient opaque constructs against static analysis. We base their resilience on the complexity of 3SAT instances with cn clauses for c = 6 and n distinct variables. We draw on existing theoretical bounds to show that these instances always require exponential time to defeat under formal notions of resolution complexity. This paper also explores in-depth the security of opaque constructs in real-world settings. We argue that the common theoretical model used in prior work (as well as our resilient opaque construction scheme) is too optimistic. It does not offer practical obfuscation against an adversary who tolerates some small false positive rate. We offer a heuristic-based attack to demonstrate this issue. Our results suggest that opaque constructs should be viewed with a high degree of skepticism until they can be proven secure under more useful theoretical models.
展开▼
