Steganographic messaging system using code invariants
A steganographic method to prevent the execution of malicious code and mitigate software piracy. The method uses invariant portions of machine instructions to create an executable watermark within unmodified code. This watermark can be verified at any stage of the software lifecycle, including dynamically and continuously during execution, to detect foreign code by verifying the integrity of the watermark prior to execution. In addition, the watermark may serve as a steganographic covert channel concealing additional information. Code invariants are not altered by binding operations such as loading and linking on different machines, and thus may be employed to consistently and repeatedly identify an unmodified instantiation of a particular program. The use of opcodes and register references as invariants avoids trivial register substitution as a means of program differentiation that eludes detection. The split key structure of the resulting cipher implies that knowledge of only the code (first key) or the cipher table (second key) alone is insufficient to derive the message.
1. A method for encoding steganographic messages comprising:
parsing, from a code segment, a sequence of invariants, the invariants corresponding to fixed values in a microprocessor instruction sequence, each invariant defined by an invariant symbol;
selecting a message from a sequence of message symbols from an alphabet; and
defining a translation alphabet by mapping each message symbol in the selected message to a successive invariant in the sequence of invariants, the mapping associating each of the invariant symbols to a subset of the message symbols from which the message is composed, the mapping defining the message in the unmodified sequence of invariants from the code segments that leaves the instruction sequence unchanged, each occurrence of an invariant symbol associated with a plurality of message symbols in the subset of symbols.
2. The method of claim 1 further comprising
binding each invariant symbol from the sequence of invariants to a message symbol from the sequence of message symbols, the binding defining the translation alphabet from a non-injective mapping of the invariant symbols to the message symbols.
3. The method of claim 1 wherein each message symbol of the message has a corresponding invariant defined by a corresponding position in each respective sequence such that the invariant symbol has maps to multiple message symbols, the set of parsed invariants defining a translation alphabet having multiple translations in the message symbols resulting from the same invariant symbol.
4. The method of claim 3 further comprising authenticating the code segment by validating each symbol in the message against the set of symbols associated with the corresponding invariant symbol from the sequence of invariants.
5. The method of claim 3 further comprising mapping each invariant to a symbol in the message, the message configured for subsequent validation of the code segment by mapping each symbol of the message to the corresponding invariant, each occurrence of a particular invariant independent of the mapping applied to other occurrences of the same invariant.
6. The method of claim 1 further comprising authenticating the code segment by:
retrieving the message;
parsing each invariant from the code segment;
identifying the set of symbols to which each parsed invariant corresponds;
comparing, in an iterative manner, each successive symbol of the message to the set of symbols corresponding to each successively parsed invariant; and
confirming if each successive symbol is in the set of symbols corresponds to the respective parsed invariant.
7. A computer program product having computer program code encoded as a set of instructions on a non-transitory computer readable storage medium that, when executed by a processor, cause the computer to perform a method for encoding steganographic messages by invariant recognition, the method comprising
parsing, from a code segment, a sequence of invariants, the invariants corresponding to fixed values in an instruction sequence, each invariant defined by an invariant symbol;
selecting a message from a sequence of message symbols from an alphabet; and
defining a translation alphabet by mapping each message symbol in the selected message to a successive invariant in the sequence of invariants, the mapping associating each of the invariant symbols to a subset of the message symbols from which the message is composed, each occurrence of an invariant symbol associated with a plurality of message symbols in the subset of symbols the mapping defining the message in the unmodified sequence of invariants from the code segment that leaves the instruction sequence unchanged.
8. The method of claim 1 wherein each invariant symbol maps to multiple message symbols, the set of parsed invariants defining a translation alphabet having multiple translations in the message symbols resulting from the same invariant symbol.