US 7,356,463 B1Grant
System and method for detecting and decoding semantically encoded natural language messages
Issue Date:2008-04-08
•16 Claims
•5 Drawing Sheets
Abstract
A system detects and decodes semantic camouflage in natural language messages. The system is adapted to identify entities such as words or phrases in overt messages that are being used to disguise different and unrelated entities or concepts. The system automatically determines the semantic plausibility of the overt message and identifies entities that appear in implausible contexts. In addition, the system automatically estimates covert meanings for the entities identified in the overt message that appear in implausible contexts.
Metadata
Assignee
- Xerox Corporation
Inventor
- Pierre Isabelle
Application Information
Application Number:US 10/737,975
Filing Date:2003-12-18
Priority Date:2003-12-18
Art Unit:2626
Classifications
IPC:
G06F17/27
Patent Drawings (5 sheets)
Description
Background of Invention
[0001] The present invention relates generally to a steganalytic method and apparatus for detecting and decoding semantically encoded natural language.
[0002] Generally, cryptography and stenography relate to the art of information hiding while cryptanalysis and steganalysis relate to the art of discovering how the information was hidden.
[0003] Cryptography, which includes encryption and decryption, involves scrambling a message using a key so that only those who have the key may descramble it. More specifically, encryption systems perform an encryption operation on a plaintext message using an encryption key to produce a ciphertext message that is not understandable but that is still visible. The receiver of a ciphertext message performs a corresponding decryption operation with a decryption system using a decryption key to recover the plaintext message. Cryptanalysis involves identifying the key. Additional background on cryptography is disclosed by Kahn, in “The Codebreakers: the Story of Secret Writing,” second edition, Scribner, New York, 1996 (original ed.: MacMillan, 1967), which is incorporated herein by reference and referred to below as “The Codebreakers”).
[0004] In contrast, steganography concerns techniques for hiding messages in such a way that their presence cannot be seen in the plaintext message. Thus, unlike cryptography which produces a visible message that cannot be understood without the appropriate key, steganography produces a visible message that can be understood but contains a hidden meaning within the visible message. Steganalysis is the art of detecting the steganographic meaning of the hidden message. Additional background on steganography and steganalysis is disclosed by Neil F. Johnson, in “Steganalysis”, Chapter 4 of Stefan Katzenbeisser (ed.), Fabien A. P. Petitcolas (ed.), “Information Hiding Techniques for Steganography and Digital Watermarking”, Artech House Books, 2000, which is incorporated herein by reference.
[0005] As defined herein, “semantic camouflage” refers to a subset of steganographic techniques, which subset includes those techniques used to hide a covert message in an overt message by performing a natural language transformation. The overt message is one that can be read on the face of the plaintext message. However, with additional information that describes the natural language transformation, the covert message may be uncovered. For example, a group of people may set up a convention for carrying out conversations between themselves where any reference to some illicit substance is to be made using a reference to “flowers”. Their conversations could thereafter involve a discussion concerning the quality, age, variety, and quantity of the illicit substance without ever having to identify it as such in the conversation.
[0006] Others have described semantic camouflage. For example, Kahn in The Codebreakers describes “jargon code” that was used by spies during the 20th century World Wars and the efforts of counter-intelligence services to intercept such coded messages through censorship activities. More specifically, Kahn in The Codebreakers at page 519 discloses that: “Censorship defends itself against this ruse by a feel for stilted or heavy-handed language and by a healthy skepticism concerning subject matter.” Such interception of semantically camouflaged messages is based on a (manual) human assessment of whether the message is believable.
[0007] Yet others have described semantic camouflage as the field of “forensic linguistics”, which is the study of linguistic evidence that can be brought to bear in legal contexts. One special case is the study of evidence indicating that the participants in some particular conversation might be making use of coded language with the intent to deceive. For example, Shuy in “Discourse Clues to Coded Language in an Impeachment Hearing” (published in G. Guy, C. Feagin, D. Schiffrin and J. Baugh, Eds., “Towards a Social Science of Language: Papers in Honor of William Labov”, Amsterdam: John Benjamins, 1997, pp. 121-138), describes a report by an expert in forensic linguistics on a study conducted as part of a legal trial in order to assess whether a taped conversation showed any evidence of “partial and disguised codes”.
[0008] Semantic camouflage is distinct from other steganographic techniques which involve concealing a ciphertext message as innocuous text. An example of such a system is disclosed by M. Chapman and G. Davida, in “Hiding the Hidden: A Software System for Concealing Ciphertext as Innocuous Text,” International Conference on Information and Communications Security, Nov. 11-13, 1997, Beijing, P. R. China, in which an encrypted message is made to look like ordinary language using a number-to-word dictionary that turns visibly encrypted messages into something that looks like ordinary language, so as to escape notice from potential code-breakers.
[0009] Also, semantic camouflage is distinct from null ciphers which involve spreading parts of covert messages in discontinuous portions of overt or plaintext messages (e.g., where each part of a message may be spread at a character level, word level, or bit level). For example, a covert message may be spread over elements of a plaintext message using a cipher-key which states that every nth word of the plaintext message belongs to the covert message. While spreading words rather than characters may be easier for encoding and decoding, it has the drawback that potentially sensitive words of the covert message will appear overtly.
[0010] Semantic camouflage has certain advantages over other steganographic techniques such as null ciphers because of the simplicity in which it may be used to code and decode covert messages. Indeed, coding and decoding is easy enough that it can be used in real-time and thus in day-to-day conversations. Moreover, while coding and decoding rules of semantic camouflage will typically be agreed upon in advance, in some situations it is possible for the encoder to define simple camouflage rules without prior agreement, letting the recipient infer these rules from his knowledge of the situation (e.g., a bookie calls a long-time client and asks him if he wanted to play, the client may well infer that the word “play” is being used to mean “bet” even if that was not agreed upon in advance).
[0011] Thus, while semantic camouflage is related to steganographic techniques such as null ciphers, semantic camouflage involves transforming the meaning of a plaintext message rather than by spreading over it parts of a covert message. More specifically, the coding and decoding rules of semantic camouflage are defined using a set of semantic transformations that specify the translation between an overt linguistic unit and its covert meaning (e.g., “bet” is expressed as “play”). Such rules resemble encryption, in that they specify “how to code” rather than “where to hide” (e.g., the null cipher key). But unlike typical cryptographic encryption which transforms the form of a plaintext message, semantic camouflage involves transforming the meaning of a message. Thus, where usual encryption methods will encode two synonym words in completely different ways, semantic camouflage is expected to encode synonyms in the same way (e.g., “play” would be used to encode both “bet” and “gamble”).
[0012] Producing a good semantically camouflaged message is more subtle than simply transforming a series of individual words. Instead, it amounts to adopting one or more suitable metaphors in which events and situations are meaningfully transposed. Complex metaphors are not readily defined on-the-fly because they generally require agreement in advance. In addition, a metaphor may not always be used consistently because new events may occur that may not be readily described using the agreed upon metaphor. Because of these difficulties, the use of semantic camouflage is often imperfect.
Summary of Invention
[0013] In accordance with the invention, there is provided a system, method and article of manufacture therefor, that takes advantage of imperfect use of semantic camouflage to automatically detect and decode its presence in natural language messages. Generally, the system is adapted to identify the relative lack of semantic plausibility that semantic camouflage transformations tend to induce on overt messages. More specifically, the system is adapted to identify entities such as words or phrases in overt messages that are disguised using different and unrelated entities or concepts. In accordance with one aspect of the invention, the system automatically determines the semantic plausibility of the overt message and identifies entities that appear in implausible contexts (i.e., entities unlikely to appear in the context of the overt message). In accordance with another aspect of the invention, the system automatically estimates covert meanings for the entities that are identified as being used in an implausible context.
[0014] In accordance with yet another aspect of the invention, there is provided a method, apparatus and article of manufacture therefor, for a method for detecting semantically encoded natural language in textual input data. Initially, the textual input data is segmented into a plurality of token linguistic units to define a linguistic event. Subsequently, one or more token linguistic units in the linguistic event are assigned a context. Each context, which is assigned to a token linguistic unit in the linguistic event, has at least one linguistic relation that relates the token linguistic unit in the linguistic event and at least one other token linguistic unit in the linguistic event. Finally, a score is computed for the one or more token linguistic units in the linguistic event that are assigned a context. The computed scores for the one or more token linguistic units indicate whether the token linguistic units are expected to appear with their assigned context in the linguistic event.
Brief Description of Drawings
[0015] These and other aspects of the invention will become apparent from the following description read in conjunction with the accompanying drawings wherein the same reference numerals have been applied to like parts and wherein the notation { . . . } identifies a set, [ . . . ] identifies a sequence, and < . . . > identifies a tuple, and in which:
[0016] FIG. 1 illustrates a general purpose computer system for carrying out the present invention;
[0017] FIG. 2 sets forth a flow diagram for defining a general framework for processing a language “L”;
[0018] FIG. 3 sets forth a flow diagram for estimating parameters of a probability model P(u,C); and
[0019] FIG. 4 illustrates details of the semantic camouflage detector and decoder module shown in FIG. 1 .
Detailed Description
[0020] A. Framework for Processing Semantic Camouflage
[0021] FIG. 1 illustrates a general purpose computer system 110 for carrying out the present invention. The system 110 includes hardware 112 and software 114. The hardware 112 is made up of a processor (i.e., CPU) 116, memory 118 (ROM, RAM, etc.), persistent storage 120 (e.g., CD-ROM, hard drive, floppy drive, tape drive, etc.), user I/O 122, and network I/O 124. The user I/O 122 can include a keyboard 126, a pointing device 128 (e.g., pointing stick, mouse, etc.), microphone 108, camera 104, speakers 106, and the display 130. The network I/O 124 may for example be coupled to a network 132 such as the Internet. The software 114 of the system 110 includes an operating system 136, a text extractor 138 and semantic camouflage detector/decoder module 140. The memory 118 includes a priori knowledge 408, language database 412, probability model P(u,C) 415, and linguistic relations 416 which are shown in FIG. 4 and described in more detail below.
[0022] Generally, the system 110 receives input data 150 through I/O 122 or 124 that is reduced to a linguistically analyzable form (e.g., words, phrases, n-grams, etc.). The input data 150 may be in the form of video, audio, textual, and/or image data. The form of the input data 150 may be one that can be input directly to the module 140 or may require pre-processing by text extractor 138. From the input data 150, the system 110 estimates the context in which the input data was used. The system 110 then determines whether the estimated context in which the input data was used is plausible. If the input data is determined to be used in implausible contexts, its covert meaning or context is estimated. The system 110 may thus provide as output data 152, a warning that input data 150 was used in an implausible context along with an estimated context in which the input data 150 was intended to be used.
[0023] B. General Framework for Processing Language
[0024] The general framework defined herein for processing natural language uses the relevant notion of semantic plausibility of a linguistic event E of natural language L as a function of the similarity between the way token linguistic units (e.g., words, phrases, n-grams, etc.) that make up the linguistic event E are being used in the linguistic event E and in the natural language L as a whole. Specifically, the token linguistic units of plausible events are expected to appear in contexts that are reasonably typical for them. The term linguistic event is defined herein as any coherent linguistic manifestation of natural language L, whether the language is spoken, signed, or written and whether it involves a single party (i.e., a monologue) or several parties (i.e., a dialogue). Tokens are defined herein as instances of such linguistic units occurring in the natural language L.
[0025] A linguistic event E can be formally defined as a sequence of token linguistic units E<t1, t2 . . . tn>. Each such token linguistic unit ti represents an instantiation in the linguistic event of a corresponding linguistic unit in language L defined in a language dictionary of language database 412 and appears in a specific context C that can be formally represented as a set of contextual elements C={c1,c2 . . . ,cn} in which each contextual element ci is a tuple <rf, t1 . . . th> made up of a linguistic relation rf that holds between token linguistic unit ti and the other token linguistic units t1 . . . th, where ti≠t1 . . . th of the same event. The linguistic relation rf is drawn from a set of R={r1, r2 . . . rk} of linguistic relations (for example, as stored in memory at 416 in FIG. 4 ).
[0026] Generally, token linguistic units t in a linguistic event E may include any kind and/or combination of linguistic units, and the relations may include any kind of linguistic relation. In one embodiment, relations r in the set of linguistic relations R stored in memory 416 includes one or more of a combination of (a) co-occurrence relations (e.g., linguistic unit A co-occurs with linguistic unit B within a window of N linguistic units), (b) morphological relations (e.g., linguistic unit A and linguistic unit B are related to root C), (c) syntactic relations (e.g., linguistic unit A, which is a noun, is the subject of linguistic unit B, which is a verb), (d) semantic relations (e.g., linguistic unit A is the agent of linguistic unit B), and (e) discourse relations (i.e., cross-sentence relations that include co-reference relations and temporal sequences between actions; e.g., cross-sentence relation between linguistic unit A which is a pronoun and linguistic unit B, which is an antecedent).
[0027] It will be appreciated by those skilled in the art that many other linguistic relations not described herein may form part of the set of linguistic relations R stored in memory 416. Any such linguistic relation generally describes how token linguistic units in a linguistic event relate to other token linguistic units in the linguistic event. For example, semantic relations may identify relationships in the universe of interpretation between the entities denoted by the linguistic units of a linguistic event (for example, being the agent or the recipient of some action, such as the perpetrator and the victim, respectively, of a crime). It will further be appreciated that such semantic relations are often coupled with syntactic relations (for example, the syntactic subject of the English verb “hit” is associated with an agent role and its syntactic object with a victim role). Some important factors that are identified for evaluating the relation of two token linguistic units include: the order in which token linguistic units are used in a linguistic event; and the repetition of the same token linguistic unit throughout a linguistic event.
[0028] For example, in a semantically transformed message that uses the concept “bedtime story” to camouflage the concept “bomb”, the context of the token linguistic unit “bedtime story” is found to include the following relations in the linguistic event (additional background of such a semantically transformed message is described in the publication entitled “Language and National Security, Language in Intelligence”, published by the National Foreign Language Center at the University of Maryland on the Internet at http://www.nflc.org/security/lang_terror.htm): (a) it co-occurs with the linguistic units: prepare, oil, fertilizer, warehouse; (b) it is the syntactic object of the linguistic unit: prepare; and (c) it is the complement of: warehouse. In this example, the linguistic units are words and the linguistic relations between the linguistic units are co-occurrence or syntactic dependencies of some kind. By evaluating how likely the token linguistic unit “bedtime story” is used with such relations in its assigned contexts within the message, the invention takes advantage of imperfect use of semantic camouflage to automatically detect implausible uses in the linguistic event of token linguistic units in their assigned contexts.
[0029] FIG. 2 sets forth a flow diagram for defining a general framework for processing events of a language “L” that may originate from, for example, input data 150 or an assembled corpus. The corpus may for example be the British National Corpus (BNC), which is a collection of samples of written and spoken language designed to represent a wide cross-section of current written and spoken English.
[0030] Initially at 202, a set of linguistic units “U” (i.e., U={u1, u2 . . . um}) of natural language “L” is defined. These linguistic units may, for example, be words, n-grams, or phrases. The natural language L is made up of linguistic events “E”. Each linguistic event E consists of a sequence of tokens of linguistic units from the set of linguistic units U. For example, the linguistic event Ej may consist of the sequence of token linguistic units [t1, t2 . . . tn], where each token linguistic unit ti in the sequence is an instance of some linguistic unit uj of U.
[0031] At 204, a set of linguistic relations “R” (i.e., R={r1, r2 . . . rk}) (stored at 416 in FIG. 4 ) that can hold between tuples of linguistic units in any linguistic event E is defined. Each linguistic relation “r” in the set of linguistic relations R is assigned an arity Ar(r), which specifies a fixed number of linguistic units between which the linguistic relation may hold (i.e., generally “arity” is the number of arguments a function or operator takes). For example, a binary linguistic relation rb has an arity Ar(rb) equal to two.
[0032] At 206, a function “F” is defined. The function F takes as input a single linguistic event E and segments it into a sequence of token linguistic units (i.e., E=[t1, t2 . . . tn]). Further, the function F attaches to each token linguistic unit ti in the sequence of linguistic units a context Ci, thereby transforming the linguistic event E into a sequence “S” of unit-context pairs (i.e., S=[<t1, C1>, <t2, C2> . . . <tn, Cn>]). Each context Ci of token linguistic unit ti is a set of contextual elements (i.e., Ci={c1, c2 . . . cw}). Each contextual element cm in the set of contextual elements is made up of: (1) a linguistic relation rf from the set of linguistic relations R; and (2) h=Ar(rf)−1 other token linguistic units from the same linguistic event E. In other words, each contextual element c=<rf, t1 . . . th> in the set of contextual elements Ci is provided such that: ti≠t1 . . . th; rfεR; and the relation rf holds between the token linguistic unit ti and the token linguistic units t1 . . . th.
[0033] To recapitulate, for each different natural language L processed by the system 110, there is defined at 202, 204, and 206:
[0034] U={u1, u2 . . . um}, a set of linguistic units of natural language L;
[0035] E=[t1, t2 . . . tn], a linguistic event E made up of a sequence of token linguistic units, with each token linguistic unit identifying an instance of such linguistic unit occurring in the natural language L;
[0036] R={r1, r2 . . . rk}, a set of linguistic relations that can hold between token linguistic units in the linguistic event E, and where each relation in the set of linguistic relations is typed for its arity; and
[0037] F, a function that reduces the linguistic event E of natural language L to:
[0038] S=[<t1, C1>, <t2, C2> . . . <tn, Cn>], a sequence of unit-context pairs, where
[0039] Ci is a context of token linguistic unit ti that is made up of a set of contextual elements {c1, c2 . . . cw}, and where
[0040] c=<rf, t1 . . . th> provides that each contextual element c in the set of contextual elements is made up of a relation rf from the set of linguistic relations and h=Ar(rf)−1 other token linguistic units from the same linguistic event E.
[0041] Given this general framework, a probability model P(u,C) can be defined on contexts C for linguistic units u in the set of linguistic units U. FIG. 3 sets forth a flow diagram for estimating parameters of the probability model P(u,C). The probability model is one embodiment for estimating the likelihood that a linguistic unit u occurs in the context C. In alternate embodiments, this likelihood can be estimated using approximation techniques that define weights that are not based on sound probability models where decisions are made on the basis of intuitions instead of statistics. In a sound probability model, the probability of all choices should sum to one at each choice point, which need not be the case in such approximation techniques.
[0042] Estimating the parameters of the probability model P(u,C) may be briefly summarized as follows. Initially, a large number of linguistic events of natural language L are collected. The function F, described above, is applied to the corpus VL so as to extract from it tokens of linguistic units ti, each one with its respective context Ci. For each linguistic unit u appearing in VL, a probability model P(u,C) may be estimated by considering all token linguistic units t of u in VL and performing statistical counts on the contexts associated with these token linguistic units.
[0043] Depending on the details of the probability model, some simplifying assumptions may be required in order to perform its estimation. For example, with some probability models it might be useful to assume that the elements of a context C={c1,c2 . . . ,cn} are statistically independent, even though this may not be true in practice. Moreover, some probability smoothing may be required so as to render the probability model robust in the face of events that may not have been observed in the corpus.
[0044] With reference again to FIG. 3 , the details for estimating the probability model P(u,C) are described. At 302, a corpus VL of events E of natural language L is collected. It will be appreciated by those skilled in the art that collecting the corpus VL may be fully automated so that it may be applied to process very large amounts of linguistic data, and thereby record in the corpus a large quantity of plausible linguistic events.
[0045] At 304, the function F defined at 206 in FIG. 2 is applied to each event E (1 . . . y) of corpus VL to transform the corpus VL into a single sequence “Q” of unit-context pairs: S1+S2 . . . +Sy=[<t1, C1>, <t2, C2> . . . <tn, Cn>], where n is the length of the corpus in number of linguistic units.
[0046] At 306, the single sequence Q of unit-context pairs is used to estimate the probability model P(u,C).
[0047] In a first method for estimating a probability model at 306, a corpus is collected at 302, which has a sufficient number of samples of data to accurately account for the interaction of interdependent contextual elements “c” in events E of the natural language L. Such a corpus is used at 306 to estimate the probability model P(u,C). In an embodiment with a corpus comprising N linguistic units, the data over which the probabilities are estimated is a set of unit-context pairs (i.e., {ui,Ci}, where i=1 . . . N). The probability model P(u,C) for the corpus may then be estimated using the maximum likelihood estimate given by:
[0048]
where:
where:
[0049] “#” is the number of elements contained in (or cardinality of) the set { } to which # is attached,
[0050] “u” belongs to U={u1, u2 . . . um}, the set of linguistic units of natural language L,
[0051] “ti” is the ith token linguistic unit appearing in the corpus VL that comprises a total of N token linguistics units,
[0052] “Ci” is the context associated with the linguistic unit ui, and made up of interdependent contextual elements “c”,
[0053] and where P(u) and P(C) may be computed by marginalizing P(u,C) using, respectively:
[0054]
[0055] and further where P(u|C) may be computed using the relation:
[0056]
[0057] In second method for estimating a probability model at 306, a corpus is collected at 302 that requires less sample data. Such a corpus is used at 306 to approximate probabilities for the probability model P(u,C) using the Naïve Bayes independence assumption between the elements cj of context C using the following equations and relations (where ti is the ith token linguistic unit appearing in the corpus VL that comprises a total of N token linguistic units):
[0058]
[0059] Upon developing a probability model P(u,C) at 306 using either method, the probability model P(u,C) for the corpus VL is stored in memory 118 of the system 110 shown in FIG. 1 for use by the semantic camouflage detector and decoder module 140, as shown in more detail at 415 in FIG. 4 .
[0060] C. Exemplary Embodiments for Processing Language
[0061] FIG. 4 illustrates details of the semantic camouflage detector and decoder module 140 shown in FIG. 1 . Input data (or observed natural language data) 150 may, for example, take the form of text data or image/audio data. In the case of text data, the input data is input directly to the detector and decoder module 140. In the case of image/audio data the text extractor 138 extracts text from image and/or audio data through means known in the art. The textual output of the text extractor 138 is input directly to the module 140.
[0062] Upon receipt of input data 150 in the form of text (i.e., whether or not pre-processed by text extractor 138), a segmentation module 410 segments the text input into a sequence of token linguistic units ti using language database 412 to define a linguistic event E (i.e., E=<t1, t2 . . . tn>). In one embodiment, the text segmentation module 410 tokenizes the text input at word boundaries and/or phrase (i.e., multiword) boundaries. The language database 412 includes linguistic units of one or more language dictionaries that are used to perform text segmentation. The language dictionary from the language database 412 that is used to process the input text may for example be chosen using a language guesser or identified in advance.
[0063] A context computation module 414 applies the function F, as defined at 206 in FIG. 2 , that takes the linguistic event E defined by module 410 and attaches to each (or, alternatively, one or more) token linguistic unit ti of the linguistic event E a context Ci to produce a sequence of unit-context pairs S (i.e., S=[<u1, C1>, <u2, C2> . . . <un, Cn>]). As set forth above, each context Ci of each token linguistic unit ti in the sequence of unit-context pairs S is a set of contextual elements such that each contextual element c in the set of contextual elements C is made up of a relation r from the set of linguistic relations 416 and at least one other token linguistic unit u from the linguistic event E.
[0064] A score computation module 418 assigns a score (e.g., P(u|C)) to each token linguistic unit ti for its context Ci in the sequence of unit-context pairs S of the linguistic event E using the probability model P(u,C) derived from corpus VL stored at 415 and produced as described above with reference to FIG. 3 . The score provides an estimate of the plausibility that the token linguistic unit ti should appear in its context Ci in the linguistic event E.
[0065] A context verification module 420 determines whether token linguistic units ti for the linguistic event E have likely been used in an implausible context (or alternatively in a plausible context). The determination that the linguistic event E defined at 410 is likely used in an implausible context is output as warning (or output) data 152. In one embodiment, the warning data is provided with anomalies highlighted in the input data (i.e., linguistic units that are identified as being used in implausible contexts). In another embodiment, the warning data is a signal that indicates anomalies have been identified in the input data but does not identify the anomalies.
[0066] As computed at 418, the plausibility of the linguistic event E, which is made up of token linguistic units <t1,t2 . . . ,tn> that have assigned contexts <C1,C2 . . . ,Cn>, depends on the value of P(u|Ci) for its token linguistic units ti. It will be appreciated by those skilled in the art that there exists various ways to define, at 420, the plausibility of the linguistic event E on the basis of the plausibility of its individual components P(u|C).
[0067] In one embodiment, the plausibility of the linguistic event E is equated with the lowest scoring value of P(u|Ci) in the linguistic event E, thus drawing attention to linguistic units that are being used in the most implausible way. However, because a judgment based on a single value P(u|Ci) is inherently less robust to noise in the input data, various filters may need to be added, such as for example a filter to disregard rare linguistic units because the probability estimates associated with them may be unreliable. In addition as part of this embodiment or forming part of a separate embodiment, a plausibility threshold may be determined (e.g., empirically) below which low scoring linguistic units or low scoring linguistic events may be flagged as potentially being camouflage.
[0068] Generally, camouflage detection at 420 identifies a low plausibility value for token linguistic units in the overt message (i.e., input data), which in turn relies upon some token linguistic units ti of that overt message appearing in unlikely contexts Ci, that is, with particularly low values for P(u|Ci). Such low values raise the suspicion that the presence of the token linguistic unit ti is actually the result of applying a camouflage recoding rule, such as: all tokens of some unknown (camouflaged) linguistic unit uj are recoded as tokens of linguistic unit ui. In one embodiment at 420, all values of p(u|Ci) that fall below the predetermined plausibility threshold are assumed to be a side effect of some camouflage recoding rule and will be flagged as such.
[0069] In addition, a covert meaning estimation module 422 may form part of (or alternatively be operationally separate from) the decoder/detector module 140 to estimate covert meanings of token linguistic units t identified as having been used in implausible contexts (and/or highlighted as anomalies in the input data). If ti is a token of linguistic unit ui and ti appears in context Ci and the value of P(ui|Ci) is such that it is found likely that the tokens of some unknown linguistic uj are being camouflaged as tokens of ui, then one or more possible values for uj may be estimated by selecting one or more linguistic units u for which the value P(u|Ci) is maximal (or more probable).
[0070] The covert meaning estimation module 422 thus enables the reconstruction of one or more hypothesized camouflage recoding rules in, for example, the form where token linguistic unit uj is assigned to linguistic unit ui. In reconstructing the hypothesized camouflage recoding rules, a list of one or more values for each hypothesized covert token linguistic unit may be provided as output data 152 (possibly including a value indicating their likely probability in the context).
[0071] Those skilled in the art will appreciate that the method described above for estimating hypothesized meanings for a camouflage recoding rule assumes that the context Ci was not distorted by additional camouflage recoding rules. When such distortions occur, the module 140 is required to take these additional dependencies into account.
[0072] In another embodiment of the semantic camouflage detector/decoder module 140, a priori knowledge stored at 408 is used to help determine what is likely or unlikely to be recoded. Without using a priori knowledge 408, all linguistic units u of language L are taken to be equally likely to appear in the input or output of camouflage recoding rules.
[0073] In this alternate embodiment that uses a priori knowledge 408, the detector/decoder module 140 may be customized/optimized for specific classes of covert messages (e.g., for a class of messages concerning drug transactions). That is, the detector/decoder module 140 in this alternate embodiment is adapted to increase its relative performance through the addition of some amount of domain-specific a priori knowledge. For example, the input data may include in addition to text data, context data that is associated with the text and/or image/audio data received at 150. Such context data may be received and/or produced using one or a combination of the input data 150 (e.g., evaluate an image to identify objects and/or locations) and data from one or more additional input sources (e.g., a third party data source identifying location where input data is produced), and thereafter stored in memory 408 that records a priori knowledge for input data 150.
[0074] The context data stored in memory 408 may be advantageously used in an alternate embodiment to limit the range of potential camouflage recoding rules to those that happen to recode some particular sets of linguistic units. For example, if to the camouflage detector/decoder module 140 is intended to operate primarily with camouflaged drug transactions, linguistic units such as like “drug” are more likely to be recoded than linguistic units such as “flower”. The linguistic unit “drug” may thus be declared part of a “sensitive” subset of linguistic units ULS⊂UL that will be considered as candidates for camouflage. Potential sets of camouflage recoding rules may then be partial functions such as: subset of linguistic units ULS is assigned to subset of linguistic units UL-ULS.
[0075] Restricting the domain of potential camouflage rules to a sensitive subset of linguistic units ULS has a potential beneficial impact on both the detection and decoding performed by the module 140 at 420 and 422, respectively. At the detection stage, generally linguistic unit uj that appears in low-plausibility contexts Ci is identified because this may indicate that linguistic unit uj is a camouflage for some other linguistic unit. But this entails that the only contexts in which interest is sought are those contexts that constitute good contexts for one or more of the linguistic units in the sensitive subset of linguistic units ULS. Suppose for example that the score p(ui|Ci) falls below some predetermined threshold that makes it a candidate for camouflage. Then, the module 140 may at 420 verify that there exists some ujεULS such that p(uj|Ci) has a high value. If not the low value of p(ui|Ci) may be regarded by the module 140 at 420 as noise in the data. As a result, the precision of detecting linguistic units likely used in implausible contexts at 420 may be increased. Similarly, when estimating covert meanings at 422, considering possibilities that are only within the sensitive subset of linguistic units ULS may also increase decoding precision.
[0076] D. Miscellaneous
[0077] Using the foregoing specification, the invention may be implemented as a machine (or system), process (or method), or article of manufacture by using standard programming and/or engineering techniques to produce programming software, firmware, hardware, or any combination thereof. It will be appreciated by those skilled in the art that the flow diagrams described in the specification are meant to provide an understanding of different possible embodiments of the invention. As such, alternative ordering of the steps, performing one or more steps in parallel, and/or performing additional or fewer steps may be done in alternative embodiments of the invention.
[0078] Any resulting program(s), having computer-readable program code, may be embodied within one or more computer-usable media such as memory devices or transmitting devices, thereby making a computer program product or article of manufacture according to the invention. As such, the terms “article of manufacture” and “computer program product” as used herein are intended to encompass a computer program existent (permanently, temporarily, or transitorily) on any computer-usable medium such as on any memory device or in any transmitting device.
[0079] Executing program code directly from one medium, storing program code onto a medium, copying the code from one medium to another medium, transmitting the code using a transmitting device, or other equivalent acts may involve the use of a memory or transmitting device which only embodies program code transitorily as a preliminary or final step in making, using, or selling the invention.
[0080] Memory devices include, but are not limited to, fixed (hard) disk drives, floppy disks (or diskettes), optical disks, magnetic tape, semiconductor memories such as RAM, ROM, Proms, etc. Transmitting devices include, but are not limited to, the Internet, intranets, electronic bulletin board and message/note exchanges, telephone/modem based network communication, hard-wired/cabled communication network, cellular communication, radio wave communication, satellite communication, and other stationary or mobile network systems/communication links.
[0081] A machine embodying the invention may involve one or more processing systems including, but not limited to, CPU, memory/storage devices, communication links, communication/transmitting devices, servers, I/O devices, or any subcomponents or individual parts of one or more processing systems, including software, firmware, hardware, or any combination or subcombination thereof, which embody the invention as set forth in the claims.
[0082] While particular embodiments have been described, alternatives, modifications, variations, improvements, and substantial equivalents that are or may be presently unforeseen may arise to applicants or others skilled in the art. Accordingly, the appended claims as filed and as they may be amended are intended to embrace all such alternatives, modifications variations, improvements, and substantial equivalents.
Claims
The invention claimed is:
1. A method for detecting semantically encoded natural language in textual input data, comprising:
segmenting the textual input data into a plurality of token linguistic units to define a linguistic event;
assigning a context to one or more of the token linguistic units in the linguistic event;
computing a score for the one or more token linguistic units in the linguistic event that are assigned a context;
applying a predetermined threshold to the score of the one or more token linguistic units to determine whether their use in the linguistic event in their assigned contexts is implausible;
estimating covert meanings of token linguistic units identified as being below the predetermined threshold; and
detecting semantically encoded natural language based on replacing all occurrences, within the linguistic event, of the token linguistic units identified as being below the predetermined threshold with the estimated covert meaning of the token linguistic units identified as being below the predetermined threshold;
wherein the computed scores for the one or more token linguistic units indicate whether the token linguistic units are expected to appear with their assigned contexts in the linguistic event; and
wherein each context, which is assigned to a token linguistic unit in the linguistic event, has at least one linguistic relation that relates the token linguistic unit in the linguistic event and at least one other token linguistic unit in the linguistic event.
2. The method according to claim 1, further comprising using a priori knowledge concerning the textual input data to estimate the covert meanings of token linguistic units identified as being below the predetermined threshold.
3. The method according to claim 1, further comprising estimating a covert meaning of a token linguistic unit when its computed score indicates that its use in the linguistic event in its assigned contexts is implausible.
4. The method according to claim 3, wherein the token linguistic units are one of words, phrases, and n-grams.
5. The method according to claim 1, further comprising estimating a probability model P(u,C) based on contexts C for a set of linguistic units U, where U is given by {u1, u2 . . . um}, occurring in a corpus VL of natural language L; wherein the scores for linguistic units in the linguistic event are assigned using the probability model P(u,C).
6. The method according to claim 5, further comprising collecting the corpus VL, of events E of the natural language L, wherein the corpus VL includes a set of linguistic units U of the natural language L, and wherein tuples of linguistic units in the set of linguistic units U have one or more relations defined therebetween that are selected from a set of linguistic relations R, where R is given by {r1, r2 . . . rk}.
7. The method according to claim 6, wherein relations in the set of linguistic relations are one or more of a combination of (a) co-occurrence relations, (b) morphological relations, (c) syntactic relations, (d) semantic relations, and (e) discourse relations.
8. The method according to claim 7, further comprising reducing linguistic events in the natural language L to a sequence of unit-context pairs S, where S is given by [<u1, C1>, <u2, C2> . . . <un, Cn>], where C, is a context of linguistic unit u, that is made up of a set of contextual elements {c1, c2 . . . cw}, and where c=<rf, t1 . . . th> provides that each contextual element c in the set of contextual elements Ci is made up of a relation rf from the set of linguistic relations and h=Ar(rf)−1 other token linguistic units from the same linguistic event E.
9. The method according to claim 1, further comprising converting audio or image input data with textual content to the textual input data.
10. An apparatus for detecting semantically encoded natural language in textual input data, comprising:
a segmentation module for segmenting the textual input data into a plurality of token linguistic units to define a linguistic event;
a context computation module for assigning a context to one or more of the token linguistic units in the linguistic event;
a score computation module for computing a score for the one or more token linguistic units in the linguistic event that are assigned a context;
a context verification module for applying a predetermined threshold to the score of the one or more token linguistic units to determine whether their use in the linguistic event in their assigned contexts is implausible; and
a covert meaning estimation module for estimating covert meanings of token linguistic units identified as being below the predetermined threshold and the covert meaning estimation module detecting semantically encoded natural language based on replacing all occurrences, within the linguistic event, of the token linguistic units identified as being below the predetermined threshold with the estimated covert meaning of the token linguistic units identified as being below the predetermined threshold;
wherein the computed scores for the one or more token linguistic units indicate whether the token linguistic units are expected to appear with their assigned contexts in the linguistic event; and
wherein each context, which is assigned to a token linguistic unit in the linguistic event by the context computation module, has at least one linguistic relation that relates the token linguistic unit in the linguistic event and at least one other token linguistic unit in the linguistic event.
11. The apparatus according to claim 10, further comprising memory for storing a priori knowledge concerning the textual input data for estimating the covert meanings of token linguistic units identified as being below the predetermined threshold.
12. The apparatus according to claim 10, further comprising:
means for estimating a probability model P(u,C) based on contexts C for a set of linguistic units U, where U is given by {u1, u2 . . . um}, occurring in a corpus VL of natural language L; and
memory for storing an estimated probability model P(u,C);
wherein the scores for linguistic units in the linguistic event are assigned using the probability model P(u,C).
13. The apparatus according to claim 12, further comprising means for collecting the corpus VL of events E of the natural language L, wherein the corpus VL includes a set of linguistic units U of the natural language L, and wherein tuples of linguistic units in the set of linguistic units U have one or more relations defined therebetween that are selected from a set of linguistic relations R, where R is given by {r1,r2 . . . rk}.
14. The apparatus according to claim 13, wherein relations in the set of linguistic relations are one or more of a combination of (a) co-occurrence relations, (b) morphological relations, (c) syntactic relations, (d) semantic relations, and (e) discourse relations.
15. The apparatus according to claim 14, further comprising reducing linguistic events in the natural language L to a sequence of unit-context pairs S, where S is given by [<ui, C1>, <u2, C2> . . . <un, Cn>], where Ci is a context of linguistic unit u, that is made up of a set of contextual elements {c1, c2 . . . cw}, and where c=<rf, t1 . . . th> provides that each contextual element c in the set of contextual elements Ci is made up of a relation rf from the set of linguistic relations and h=Ar(rf)−1 other token linguistic units from the same linguistic event E.
16. A memory device for storing a set of program instructions executable on a data processing device and usable for detecting semantically encoded natural language in textual input data, the set of program instructions comprising instructions for:
segmenting the textual input data into a plurality of token linguistic units to define a linguistic event;
assigning a context to one or more of the token linguistic units in the linguistic event;
computing a score for the one or more token linguistic units in the linguistic event that are assigned a context;
applying a predetermined threshold to the score of the one or more token linguistic units to determine whether their use in the linguistic event in their assigned contexts is implausible;
estimating covert meanings of token linguistic units identified as being below the predetermined threshold; and
detecting semantically encoded natural language based on replacing all occurrences, within the linguistic event, of the token linguistic units identified as being below the predetermined threshold with the estimated covert meaning of the token linguistic units identified as being below the predetermined threshold;
wherein the computed scores for the one or more token linguistic units indicate whether the token linguistic units are expected to appear with their assigned contexts in the linguistic event; and
wherein each context, which is assigned to a token linguistic unit in the linguistic event, has at least one linguistic relation that relates the token linguistic unit in the linguistic event and at least one other token linguistic unit in the linguistic event.
Patent Citations (3)
Non-Patent Literature (10)
- Mays et al, “Context Based Spelling Correction”, Information Processing and Management, 27(5): 517-522, 1991.Examiner
- M. Chapman and G. Davida, “Hiding the Hidden: A Software System for Concealing Ciphertext as Innocuous Text”, International Conference on Information and Communications Security, Beijing, P. R. China, Nov. 11-13, 1997.Applicant
- “Cryptography FAQ”, available on the Internet at http://www.faqs.org/faqs/cryptography-faq/, Aug. 17, 2003.Applicant
- P. Davern and M. Scott, “Steganography: its history and its application to computer based data files”, Working paper CA-0795, School of Computer Applications, Dublin City University, 1995.Applicant
- N. F. Johnson, in “Steganalysis”, Chapter 4 of Stefan Katzenbeisser (ed.), Fabien A. P. Petitcolas (ed.), “Information Hiding Techniques for Steganography and Digital Watermarking”, Artech House Books, 2000.Applicant
- N. F. Johnson, “Steganography”, George Mason University, available on the internet at http://www.jjtc.com/stegdoc/steg1995.html, 1995.Applicant
- N. F. Johnson and S. Jajodia, “Exploring Steganography: Seeing the Unseen”, IEEE Computer, 31:2, pp. 26-34, 1998.Applicant
- D. Khan, “The Codebreakers: the Story of Secret Writing”, second edition, Scribner, New York, 1996.Applicant
- National Foreign Language Center at the University of Maryland, Language and National Security, “Language in Intelligence”, available on the Internet at http://www.nflc.org/security/lang—terror.htm, 2001.Applicant
- R. Shuy, “Discourse Clues to Coded Language in an Impeachment Hearing”, In G. Guy, C. Feagin, D. Schiffrin and J. Baugh (eds), “Towards a Social Science of Language: Papers in Honor of William Labov”, Amsterdam: John Benjamins, pp. 121-138, 1997.Applicant