Abstract:
A two-stage, very fast symbol string matching mechanism measures the similarity of content between data sources, allowing for efficient detection and evaluation of exact as well as inexact matches. The disclosed approach pairs complementary encoding technique comprising a first fast lookup that identifies regions of possible similarity, and a second, more computationally intensive analysis that evaluates metrics of similarity and delimits copy boundaries. The original content remains private (encrypted) during processing.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This non-provisional application claims the benefit of provisional application No. 62/088,346, filed Dec. 5, 2014, which application is incorporated herein in its entirety by this reference. 
     
    
     TECHNICAL FIELD 
       [0002]    The present disclosure relates to information security and more specifically it relates to techniques for detecting and preventing unauthorized disclosure of sensitive information. 
       BACKGROUND 
       [0003]    With the rapid increase and advances in digital documentation services and document management systems, organizations are increasingly storing important, confidential, and/or secure information in the form of digital documents. Unauthorized dissemination of this information, either by accident or by wanton means, presents serious security risks to these organizations. Therefore, it is imperative for the organizations to protect such secure information and detect and react to any secure information (or derivatives thereof) from being disclosed beyond the perimeters of the organization. 
         [0004]    Further, the Internet facilitates wide and rapid dissemination of information. Along with obvious benefits, the ease of data access also creates challenge in controlling the flow of confidential information, such as private health and financial records, credit card numbers and social security numbers, intellectual property, software, designs, contracts, specifications, pre-release marketing materials, and business plans. This need has led to the development of a number of information security and control strategies that fall into the market category called “Data Loss Prevention”. In addition to information security, other example applications include academic institutions deterring plagiarism, copyright holders detecting infringements, and document custodians locating content. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0005]    These and other objects, features and characteristics of the present invention will become more apparent to those skilled in the art from a study of the following detailed description in conjunction with the drawings, all of which form a part of this specification. In the drawings: 
           [0006]      FIG. 1  illustrates an exemplary environment within which the embodiments of the symbol string matching mechanism introduced here may be implemented; 
           [0007]      FIG. 2  depicts a problem statement block diagram further detailing the environment of  FIG. 1  in which a symbol string matching mechanism can be implemented; 
           [0008]      FIG. 3  depicts a general solution architecture for a symbol string matching mechanism; 
           [0009]      FIG. 4  depicts an implementation of a Reference Library Constructor; 
           [0010]      FIG. 5  illustrates an example of a Signature and Entry generation and store process; 
           [0011]      FIG. 6  provides an example of a symbol stream generation process; 
           [0012]      FIG. 7  illustrates the evaluation of documents against the reference library through an analogous set of processing steps, according to some embodiments; 
           [0013]      FIG. 8  illustrates an example of the symbol string alignment and evaluation process carried out over a region of interest identified from a single entry; 
           [0014]      FIG. 9  provides an example where two entries from a single reference document match the evaluation document in relative proximity, but separated by an imperfect text sequence; 
           [0015]      FIGS. 10-13  depict an efficient method for aligning two symbol strings, representing one possible technique for implementing a Compare function; 
           [0016]      FIG. 14  depicts a flowchart depicting one embodiment of a whitelist approach; 
           [0017]      FIG. 15A  provides an example depicting one embodiment of an automated whitelisting approach in a non-alert situation; 
           [0018]      FIG. 15B  provides another example depicting one embodiment of an automated whitelisting approach in an alert situation; 
           [0019]      FIG. 16  presents one embodiment of an approach for monitoring and controlling information flow across workgroups; and 
           [0020]      FIG. 17  is a block diagram of a computer system as may be used to implement various embodiments of the described herein. 
       
    
    
     DETAILED DESCRIPTION 
       [0021]    The present disclosure may be embodied in several forms and manners. The description provided below and the drawings show exemplary embodiments of the invention. Those of skill in the art will appreciate that the invention may be embodied in other forms and manners not shown below. It is understood that the use of relational terms, if any, such as first, second, top and bottom, and the like are used solely for distinguishing one entity or action from another, without necessarily requiring or implying any such actual relationship or order between such entities or actions. 
         [0022]    Aspects, features and advantages of exemplary embodiments of the present invention will become better understood with regard to the following description in connection with the accompanying drawing(s). It should be apparent to those skilled in the art that the described embodiments of the present invention provided herein are illustrative only and not limiting, having been presented by way of example only. All features disclosed in this description may be replaced by alternative features serving the same or similar purpose, unless expressly stated otherwise. Therefore, numerous other embodiments of the modifications thereof are contemplated as falling within the scope of the present invention as defined herein and equivalents thereto. Hence, use of absolute and/or sequential terms, such as, for example, “will,” “will not,” “shall,” “shall not,” “must,” “must not,” “first,” “initially,” “next,” “subsequently,” “before,” “after,” “lastly,” and “finally,” are not meant to limit the scope of the present invention as the embodiments disclosed herein are merely exemplary. 
         [0023]    Introduced here are techniques for implementing a two-stage symbol string matching mechanism that measures the similarity of content between data sources, allowing for efficient detection and evaluation of exact as well as inexact matches. 
         [0024]    Among others, the disclosed approach specifically addresses the task of detecting and tracking files and file fragments within data stores and devices, and as they pass across networks. Example points of deployment include corporate intranets, email systems, firewalls, and private and public cloud file-sharing services. Exemplary benefits that the techniques disclosed herein may bring include: (1) Reliably detect reference information, including short data copies, potentially embedded in larger files—to achieve high true alarm rate. (2) Reliably ignore non-matching data—to achieve low false alarm rate. (3) Prove computationally efficient, capable of carrying out real-time monitoring across large data stores and networks with minimum expense. (4) Where appropriate, ignore copies of low-risk information, such as template information, marketing write-ups, disclaimers, and other public or widely disseminated information—to minimize staff time and distraction. (5) Achieve security and privacy. Specifically, the system should not retain information that would enable an adversary to recover the original data from protected reference files. 
       General Environment 
       [0025]      FIG. 1  shows one example of an overall setup to implement a document safeguard using the symbol string matching techniques introduced here. One of the means by which a user can disclose digital information outside of the organization&#39;s perimeter is by disclosing the information through his computer system  111 . Examples of such a computer system include a desktop computer, a laptop, a PDA or any such device that allows a user to access the organization&#39;s information. In one embodiment, the computing system  111  is connected to a network  125 . Through the computing system  111 , which the user accesses the organization&#39;s secure information, the user would be able to transfer information outside of the organization by transferring the information to any medium connected to the computer. 
         [0026]    Such points at which information can be transferred outside of the organization&#39;s protected environment are called egress points. Examples of transferring data at egress points include copying the information from the computer to a CD disk or any other optical storage medium, copying the information to a floppy drive or any other tape medium, copying the information to a USB key or other flash based storage medium, transferring the information by printing the information using a printer, copying information to “the clipboard” (i.e., a memory buffer) of the local operating system, transferring or copying information to a cloud-based storage or to another cloud-based service, etc. In such an event, all the information that is transmitted through the computer  111  needs to be monitored to ensure that secure or sensitive information does not get transferred. 
         [0027]    To achieve this purpose of safeguarding sensitive information, the various egress points of the computer  111  are monitored to detect any activity that purports to disclose information through the egress points. For example, a software agent (which may be called the document safeguard  115  for purposes of discussion herein) may run on the computer  111  to monitor activity at the egress points (e.g., CD disk, USB, floppy disk) associated with the computer  111 . If the organization supports more than one computer system, in some embodiments, each of these computer systems ( 111 ,  116 ,  117 ) can have copies of document safeguards installed on them to ensure that the activity on each of the computer systems is monitored. In one embodiment, the document safeguard  115  is a set of computer instructions or a computer implemented program available on a memory location (e.g., on a magnetic tape drive, a flash memory drive) at the site of the document safeguard  115 . 
         [0028]    In addition to being installed in every computer system ( 111 ,  116 ,  117 ) in the network, the document safeguards may also be installed on other vulnerable egress points across the organization. One example of such a vulnerable egress point includes one or more email server systems  118  connected to the network. The email server  118  handles and routes the emails sent out and received by the organization. The document safeguard  120  installed on the email server  118  monitors the emails desired to be sent out of the organization through the email server. Another example of a vulnerable egress point could be a print server  121  connected to the organization&#39;s network. A document safeguard  123  can be connected to or installed on the print server  121  to monitor print jobs sent by the users to the printers connected to the network. 
         [0029]    Additional examples of vulnerable egress points include network appliance systems  126 . Here, a document safeguard  128  can be installed in each network appliance in the network appliance systems  126  to ensure that information disclosed through a particular network appliance is monitored. Examples of using network appliances  126  to transfer data include sharing of data over a network share medium, data transferred at the socket or TCP layer of the network, etc. It is understood that in addition to these examples, the egress points also include other porous environments through which information can be disclosed by the user beyond the secure environment of the organization. 
         [0030]    In yet another scenario, an individual of the organization may leak the sensitive information even without passing through the individual&#39;s computer. For example, a first individual of the organization may store sensitive information on a cloud space on a computer system (e.g., cloud server  132 ) that provides cloud-based storage and/or other cloud-based services (e.g., email services, messaging, task management or workspace collaboration). A second individual of the organization who has access to the cloud space can copy the sensitive information from the first individual&#39;s cloud space to another cloud space on the cloud server  132 . In this scenario, a document safeguard  133  may be installed on the cloud server  132  to monitor and to prevent the sensitive information from being copied or transferred. Additionally or alternatively, a document safeguard server  131  may provide document safeguard as a service to, for example, the cloud server  132  so as to enable the cloud server  132  with increased data security. For example, the document safeguard server  131  can provide the document safeguard as a service via an application programming interface (API) to the cloud server  132  and/or to other computers mentioned here. 
         [0031]    In one illustrative embodiment, the computer systems and all other systems representing egress points (the egress point systems) are centrally connected to a network  125 . In one embodiment, the network includes a local network. This includes a network that is managed and maintained locally by the organization. In another embodiment, the network could also be the Internet. In the case of the Internet, each of the egress point systems could be directly and individually connected to the Internet, or could be connected to a local network or a cluster of local networks, with each of the local networks communicating with each other through the Internet. Other combinations of the egress point systems within the local network and the Internet are possible and such combinations will be apparent to a person of skill in the art. 
         [0032]    All the aforementioned sites where a document safeguard can be installed or from where a document safeguard can be provided (e.g., the user&#39;s desktop/laptop computer, one of the network appliances, etc.) are examples of vulnerable egress points in a network system. Accordingly to the present embodiments, the document safeguard can implement a symbol string matching mechanism for detecting and preventing unauthorized disclosure of sensitive information. 
       General Approach 
       [0033]      FIG. 2  depicts a problem that may be encountered in the environment of  FIG. 1 . As described in more detail below, the problem can be solved or alleviated by the techniques introduced here in a more efficient and accurate way. The problem begins with a collection of data files of interest, shown as Input  1   201 . The task is to test files on Input  2   202  to determine whether they contain one or more data subsets found anywhere within the Input  1  reference collection. Importantly, a solution must detect partial copies, such as excerpts, as well as materially similar but inexact matches. The following paragraphs describe the approach with respect to this symbol string matching mechanism. 
         [0034]    Our approach follows a two-stage data copy detection strategy: 
         [0035]    1. Identify Regions of Interest. 
         [0036]    Locate possible data matches between reference and with high positive detection rate (possibly at a high false alarm rate). This step may involve locating short exact matches, incomplete matches, or, in the case of text, may include topic or keyword recognition. At this phase of processing the system may search against large reference file collections, and needs to operate at high computational efficiencies. 
         [0037]    2. Evaluate Regions of Interest. 
         [0038]    Determine the probability of copy by estimating data similarity. This stage exhibits a low false alarm rate while retaining true detections. As it applies only to a limited set of candidates, it may employ computationally intensive techniques. 
         [0039]    The files may contain any form of data, for example text, audio, imagery, video, or arbitrary forms of binary. The disclosed technique offers particular advantages, however, when working on data characterized as symbol strings where the combination symbol value, proximity and order conveys information. Examples include human language text, numeric tabulations, database entries, and software (including source code, p-code, compiled binaries, and other forms of sequential logic). Although applicable to many data types, the descriptions below center on text to invoke intuitions helpful in understanding the technique. 
       General Architecture 
       [0040]      FIG. 3  is a general solution architecture for a symbol string matching mechanism. The General Solution Architecture ( FIG. 3 ) comprises two main functions. The Reference Library Constructor  310 , shown on the left of  FIG. 3 , processes documents to generate and store Signatures and Characterizations (Signature Store  314 , Characterization Store  315 ). Following the strategy described above: 
         [0041]    (1) Signatures enable Stage 1 by providing a first indication of similarity between files. Signatures facilitate rapid lookup into large collections of files. In some embodiments, the system can employ a cryptographic algorithm such as a secure hash algorithm (SHA) for converting large streams of data into a hash value in generating a signature. One example of the SHA that can be employed by the present techniques is SHA-256. In the examples that employ SHA-256, the resulting hash value from the SHA-256 will be 256 bits long (which is typically more than the system needs). For example, with a 12-word length text, the system implementing SHA-256 can generate a 256-bit hash value using a known SHA-256 hash function. Then, the system can, in some embodiments, select 32 bits out of the 256 bits as the signature of the text. Note that, although here the signature may not be unique to the set of words (e.g., there is a possibility that another sequence of words can also generate the same hash value or even the same signature), in many embodiments the signature is sufficient for the system to identify candidate regions of interest. 
         [0042]    Also, note that the process of selecting X number of bits from a hash value of length Y may be adjusted based on different the field applications (e.g., based on particular traits of an application, computer&#39;s workload, processing power, memory size, and/or storage size). It is observed that the length of the resulting signature may affect the storage size of the signature store that is used to store the signature. The length of the resulting signature may also affect the false alarm rate. For example, adopting 64-bit signatures may have a lower false alarm rate than adopting 32-bit signatures, but may also increase the storage space necessary for the signature store. 
         [0043]    Further, the signature selection mechanism can be chosen differently based on different applications. In one example, a 32-bit signature is the least significant 32 bits from the 256-bit hash value. In another example, the signature is the most significant 32 bits from the hash value. An additional selection mechanism example includes using a predetermined mask to generate a signature from the hash value. However, note that the signature selection mechanism should suitably remain the same for a particular application, at least for a suitable period of time, so that the same data generates the same signature. 
         [0044]    (2) Characterizations enable Stage 2 by providing an intermediate representation that preserves the information necessary to evaluate data similarity, alignment and bound (end points) of copied regions. This “soft” matching approach benefits detection of modified but substantially similar data, e.g., excerpted and edited text. Note that, if the system only employs Characterizations instead of both Signatures and Characterizations, the false alarm rate may be too high, thus rendering the match results less reliable. 
         [0045]    Also note that Signatures and Characterizations retain data privacy through use of one-way hash functions. It allows detection of data copies without exposing the original (clear text) data. 
         [0046]    The Document Evaluator  320 , shown on the right of  FIG. 3 , accepts documents and compares them against the reference collection. The evaluation process begins with Fast Lookup Signature Generator  321  and Signature Lookup  322  to retrieve candidate matches from the Reference Library Signature Store  314 ; if any signature matches are found, a more complete characterization of the evaluation document is generated in the document region surrounding the signature match  323  (Characterization Generator), and compared  324  (Characterization Comparer) against the stored characterizations for the reference documents  315  (Characterization Store). Detected copied data are output  330  (Output: Detected Region of Similar Text). 
       Specific Implementations 
       [0047]      FIG. 4  provides a particular implementation for the Reference Library Constructor  310  shown in  FIG. 3 . 
         [0048]    The implementation accepts as input a document  401  labeled with a unique identifier doc_ID. The system runs sequentially through the document, creating a non-overlapping moving window of text  402 . Process  410 , shown on the left, applies a 1st hash function  411  to a fixed-length sequence of text—words, characters, or any other convenient grouping—to generate an integer-valued Signature. An Index value is generated from the signature, either directly or derivation through a bit mask or other operation  412 . Step  413  generates an Entry containing the doc_ID, Offset and Signature, and  414  adds it to the Signature Store (corresponding to block  314  in  FIG. 3 ). 
         [0049]    Note that the Entry need not explicitly include the Signature if the storage Index and Signature are identical (in which case the signature is implied by its storage location). 
         [0050]    A second process block  420  separately processes the selected text sequence  402 . The second process block  420  generates an “intermediate representation” of the selected text sequence, and for purposes of discussion herein, the result of the process block  420  may be referred to as “characterizations.” As illustrated, a 2nd hash function converts each word (symbol, or other convenient partitioning) into an integer 421; one or more bits selected from the result  422  to generate a symbol, and concatenated into a continuous symbol stream  423  associated with the entirety of document doc ID  430 ; this store corresponds to block  315  in  FIG. 3 . 
         [0051]    Expressed as pseudo-code, adding a document to the Reference Library follows these steps: 
         [0000]    [ 401 ] do until the complete document processed:
       [ 402 ] Select a next sequence of non-overlapping words at Offset
           on a first process [ 410 ]   [ 411 ] Generate Signature by applying a 1 st  hash function to the selected sequence of words   [ 412 ] Generate Index from the Signature   [ 413 ] Generate an Entry comprising doc_ID, Offset and Signature   [ 414 ] Store Entry at an Index derived from the Signature
               on a second process [ 420 ]   
               [ 421 ] Apply a 2 nd  hash function to each word of text in sequence   [ 422 ] Save one or more bits for each word   [ 423 ] Concatenate into a symbol stream;   
           [ 430 ] When the entire document has been processed, store the resulting derived symbol stream, keyed to document doc ID       
 
         [0063]    Additional documents can be included in the reference library by re-iterating these processing steps. Further, in an embodiment, steps  412  and  421  can be built from any convenient hash function including, for example, any from the well-known SHA series. 
         [0064]      FIG. 5  illustrates the Signature and Entry generation and store process of  410 . 
         [0065]      FIG. 6  provides an example of symbol stream generation process of  420 . 
         [0066]    Conversely, a document can be removed from the reference library by reprocessing the document and removing entries associated with its signatures. Alternatively, the system may facilitate deletions by maintaining an auxiliary database that links document IDs to entries. 
         [0067]      FIG. 7  illustrates the evaluation of documents against the reference library through an analogous set of processing steps. The evaluation begins by searching for reference library entries using signatures generated from the evaluation document; and then, as necessary, generating and comparing the characterizing symbol stream against the symbol streams corresponding to the retrieved reference library documents. 
         [0068]    Expressed as pseudo-code, to test an evaluation document against a Reference Library: 
         [0000]    do until the complete document processed [ 701 ] 
         [0069]    Select a next sequence of words [ 702 ] (overlapping—shift 1 word per iteration)
       as a first step: [ 710 ], retrieve candidate Entries:
           [ 711 ] Generate Signature by applying a 1 st  hash function to the selected sequence of words   [ 712 ] Generate Index from the Signature   [ 713 ] Retrieve any Entries found at Index   
           as a second step: [ 720 ], carry out detailed comparisons
           for each retrieved Entry: [ 721 ]
               [ 722 ] Select text within the evaluation document surrounding the current text sequence   [ 723 ] Apply the 2nd hash function to selected text   [ 724 ] Save 1 or more bits for each word   [ 725 ] Concatenate to form the evaluation document symbol stream in the region of interest   [ 726 ] Retrieve corresponding symbol stream of reference library document near entry location   [ 727 ] Compare the symbol streams of reference and evaluation documents to estimate the length and similarity of copied text   [ 730 ] Aggregate and output matches   
               
               
 
         [0083]      FIG. 8  illustrates an example of the symbol string alignment and evaluation process  727  carried out over a region of interest identified from a single entry. Although not shown in  FIG. 8 , this step can also be carried out in two parts: a search left, to identify text at and preceding candidate overlap; followed by a search right, to identify text at and following candidate overlap.  FIG. 9  provides an example where two entries from a single reference document match the evaluation document in relative proximity, but separated by an imperfect text sequence; in this case, the alignment and match process evaluates the similarity of the intervening sequence to generate composite match. 
         [0084]    Alternative embodiments may incorporate other methods to preselect text of interest, including keywords or topic identification. Alternatively, structured documents may often contain confidential information in specified fields, and thus identified by recognizing and aligning with the corresponding document fields. 
       Example Alignment &amp; Matching Embodiments 
       [0085]      FIGS. 10-13  depict an efficient method for aligning two symbol strings, and represent one possible technique for implementing the Compare function  727  in  FIG. 7 . The technique identifies the minimum set of edits—deletes, substitutes, and inserts—that match a first symbol string to a second symbol string. The resulting match is then scored according to its edit distance, and compared to a threshold. The threshold indicates how many edit distances the system is set to tolerate before a potential match alert is raised, and therefore the threshold affects the alarm rate. As such, note that the false alarm rate may be higher if the threshold for edit distance is set to be 5 rather than 10 (e.g., for every 50 symbols). 
         [0086]      FIG. 10  provides an example with two similar but not identical symbol strings S 1  and S 2 , where each symbol takes on values 0 . . . 7 (i.e., 3-bit unsigned integers). In this example the input  1001  consists of 32-element S 1  and S 2  strings. Taking S 1  as the reference, S 2  differs from S 1  by three alignment errors and one symbol mismatch, comprising an edit set containing two inserts, one delete, and one substitution. This results in an edit distance of 4—that is, if all edits were weighed equally, an optimization procedure will select these four edits to best match S 2  to reference S 1 . 
         [0087]    In principle, a solution might directly carry out an exhaustive search: 
         [0088]    1. Enumerate all possible edit sets of S 2 ; 
         [0089]    2. Compare and score each candidate against S 1 ; 
         [0090]    3. Select the edit set that results in the lowest total cost. 
         [0091]    The computational complexity of this approach, however, grows exponentially with string length. 
         [0092]    Dynamic programming provides an efficient alternative means for implementing the optimization process provided that string errors occur randomly and independently. Noted that, the use of dynamic programming can also avoid local optimization problems (i.e., reaching a solution that is only locally optimized but not globally optimized). In the described procedure, computational complexity grows linearly with string length. 
         [0093]    The optimization process consists of two stages: (1) build a cumulative cost matrix that spans possible edits; and (2) identify the lowest-cost path through the matrix. 
         [0094]    As illustrated in  FIG. 11 , the first step of the optimization process generates a 2-dimensional cumulative cost matrix with row dimension n, where n is the length of reference string S 1 , and column dimension m i +m d +1, where mi and md indicate the maximum number of allowed inserts and deletes, respectively. The center column represents S 2  perfectly aligned with S 1 ; left of center represents insertions in S 2  at string position denoted by row; and right of center, deletions in S 2  at string position denoted by row. 
         [0095]    The algorithm begins by filling the top row with the cost value associated with the indicated number of deletions or insertions, e.g., the center column value=0, the immediately left cell=C i , the cost of a single insertion, its left-adjacent cell=2 C i  (cost of two insertions), etc., until reaching the left edge with cell value=m i  C 1 ; and similarly, moving right of center for deletes, values C d , 2C d , . . . m d  C d . 
         [0096]    The procedure continues to the second row, and then in each subsequent row, for every cell cc(i, j), selecting the upper adjacent cell that minimizes a cumulative cost calculated by: 
         [0000]        cc ( i,j )=min[ cc ( i− 1, j+ 1)+ C   d , //shift right: delete symbol in  S 2 with cost  C   d    
         [0000]        cc ( i− 1, j− 1)+ C   i , //shift left: insert symbol in  S 2 with cost  C   i    
         [0000]        cc ( i− 1, j )+ C   s ] //step forward with cost 
         [0000]      // C   s   =C   mm  if  S 1[ i]=S 2[ i+j ], else  C   s =0 
       Where: 
       [0097]    C i =cost of an insertion 
         [0098]    C d =cost of a deletion 
         [0099]    C s =cost of a step, either C mm  for symbol substitution (S 1  and S 2  not matching at current alignment, as denoted by S 1  at position i vs. S 2  at i+j); or C s =0 if S 1  and S 2  match. 
         [0100]    The algorithm terminates either at the bottom (nth) row, or when the cumulative cost value exceeds some allowed maximum. 
         [0101]    The process to retrieve (“unwind”) the optimal set of edits, then, operates as follows ( FIG. 12 ):
       Select the cell in the last row that contains the lowest cumulative cost value, where j may take any value in range −m i  to +m j . Store the indices (i o . j o ) and the corresponding cost value cc(i o . j o ).   Thereafter, work upward through the cost matrix:
           For the cost cell cc(i o , j o ) selected in previous iteration, choose one of the three upper adjacent cells with the lowest cost value (i.e., select one of: cc(i o −1, j o −1), cc(i o −1, j o ) or cc(i o −1, j o +1))   Save the resulting index values and edit type: if the selected cell implies a move left in the matrix, mark the edit as ‘insert’, if a move right, mark as ‘delete’; if directly above, and S[i] is not equal to S[i+j o ]), mark as ‘substitute’;   
               
 
         [0106]    Repeat until reaching the top row. 
         [0107]    The resulting list indicates the optimizing sequence of edits given the strings S 1 , S 2 , the cost constraints C i , C id  and C mm , and the maximum number of deletes or inserts md and mi, respectively. The processing complexity is on order n×(m i +m j +1).  FIG. 13  provides the output corresponding to example of  FIG. 10 . 
         [0108]    Some applications require only the similarity measure—edit distance, for example—and not the detailed list of edit types (inserts, deletes, substitutions) and locations (string offset locations of said edits). In such cases the full cost matrix need not be stored. Reviewing the optimization equation provided above, note that only the current and previous rows are required. As a result, the algorithm can rely on a 2-row circular buffer that stores only the current and previous rows (i and i−1) of the cost matrix. This drops the cost matrix size from n(2d+1) to order 2(2d+1), thus realizing a storage reduction factor of n/2. 
         [0109]    In practice this can substantially reduce memory requirements; matching two 10,000-word texts, for example, which represents about 20 pages of typical text, the approach reduces memory requirements by a factor of 5,000. 
         [0110]    The optimal sequence may yield a match cost above threshold, or may suffer significant errors on the leading or following edges of the match region. In these cases the optimizing sequences may require end pruning or segmentation: 
         [0111]    (1) Prune: delete sequence components from ends where the substrings generate high edit costs (for example, in cases of poor initial string alignment); 
         [0112]    (2) Segment: repartition the sequence into two or more shorter sequences, and remove intervening subsequences that create high match costs. 
       False Alarm Analysis 
       [0113]    “False alarms” are alerts generated through unfortunate mathematical coincidence rather than a true data copy. In a text application, for example, false alarms occur when differing text strings generate both a) an identical Signature and b) a sufficiently similar Characterization to trigger detection. In applications where false alarms are relatively rare, the false alarm probability for our two-step approach approximates to the product of the false alarm rates for each stage: 
         [0000]    
       
      
       P 
       fa 
       ˜=P 
       FA-Signature 
       ·P 
       FA-Characterization  
      
     
         [0114]    The Signature false alarm rate is set by its underlying hash function collision rate, an can be approximated by 
         [0000]        P   FA-Signature ( s )˜= k   p   /S  (false alarms per tested signature)
 
         [0115]    where k p  represents the total number of signatures of the protected documents, and S the size of the signature space (typically some large integer 2 n , where n=size of each signature in bits). 
         [0116]    The false alarm for the characterization matching process depends on the match evaluation parameters. False alarm rates P FA-Characterization  typically range 10 −7  to 10 −3 , where 10 −7  corresponds to relatively stringent match constraints (small edit distance, larger excerpts of similar text), and 10 −3  to relatively loose match constraints. 
         [0117]    To offer insights on expected false alarm rates we offer an example. An implementation may employ a 64-bit Signature, yielding S of 2 64 ˜=10 19 . A protected document collection containing 4 TB of Microsoft Word files (or similar types) represents about 200 m pages (˜100 b words) of text, and generates on order of 10 10  Signatures. This produces a P FA-Signature  on order of 10 −9 —one false alarm per one billion words evaluated. Assuming a typical P FA-Characterization  of 10 −4  we can expect a composite false alarm rate of about 
         [0000]        P   fa   =P   FA-Signature   ·P   FA-Characterization˜ =10 −9 ·10 −4 =10 −13  per evaluated word.
 
         [0118]    A 20-page evaluated document corresponds to about 10 4  words, yielding a per-document false lookup probability of 
         [0000]        P   PFA-Characterization ( s )˜=10 4 ·10 −13 =10 −9  
 
         [0119]    The experiments bear out a very low false alarm rate consistent with this result—in practice, they rarely occur. Valid but unwanted detections, however, may prove a greater challenge than false alarms, and arise from very different causes. 
       Unwanted Detections 
       [0120]    Some applications suffer from a high rate of “unwanted detections” due to true copies of inconsequential data. For example, an organization&#39;s confidential and public documents may share information, such as mission statements, addresses and contact information, marketing tag lines, product disclaimers, templates and other benign items. In practice, unwanted detections occur at a much higher rate than false alarms, and can create a content management burden for information security staff. 
         [0121]    There are at least two ways to avoid unwanted detections. The first method employs stringent matching requirements; for example, require copies to extend across most of the evaluation document. Some data loss prevention products in the market today, for example, will alert when an evaluation document overlaps a protected document by over 80%, i.e., they are substantially the same document. This requirement has the unfortunate side effect of eliminating desirable alerts, however, such as in cases of excerpts embedded in relatively large files. 
         [0122]    The second approach avoids these limitations through a special form of “white list” that identifies and allows sharing of specific information that may also reside within protected data sets. Importantly, the approach operates whitelists at the subdocument level—in text, this equates to phrases. 
         [0123]      FIG. 14  summarizes the approach. A document  14001  is evaluated against a library index of protected files  14010 , e.g., using a process as presented in  FIG. 7 . Block  14010  outputs the set of regions where the file under evaluation overlaps the protected data. These regions—for example, document fragments in a text application—are submitted to a second evaluator  14020 . The reference library for 2nd evaluator is also constructed as in  FIG. 7 , but using whitelist data. The outputs of the first  14010  and second  14020  evaluators are then compared to identify and eliminate any protected detections that also reside in the whitelist  14030 . 
         [0124]    Note that the processing blocks  14010  and  14020  can be functionally similar or even identical, but with Signature and Characterization libraries constructed with protected and whitelist files, respectively. 
         [0125]    The general approach to whitelisting can take various embodiments, where the specifics depend on the application. There are two examples: 
         [0126]    (1) Manual. If the set of whitelist material is well established and available, the whitelist library can be created by manually feeding a reference constructor (as in  FIG. 4 ) with whitelist data. In a document application, whitelist files may contain standard forms and templates, corporate marketing, common legal disclaimers, and other non-sensitive information. The manual approach has the drawback of requiring security staff vigilance to maintain accurate whitelists. 
         [0127]    (2) Automated. A second approach eliminates the need for manual whitelisting by monitoring file content location and flow (at the file fragment level). The solution strategy centers on information risk management: identifying (and possibly stopping) the flow of protected data that has not been previously shared, while allowing sharing of previously released data. With this approach the system will automatically ignore common data fragments such as described above (templates, corporate marketing, etc.). 
         [0128]      FIGS. 15A and 15B  respectively provide a graphical example. A File A  15001  is considered for release into a Destination  15010 , where the destination represents the group of users who can access the file after transfer, e.g., a personal or workgroup folder in a content management system (CMS), including cloud-based filesharing, or Enterprise CMS systems such as SharePoint; with another company; or at-large public. File A is evaluated against a protected file set  15020  to identify possible content overlap, resulting (in this example) in two identified fragments, labeled as i and ii. The detected overlaps are then compared against the existing content at Destination  15010 . In the example of  FIG. 15A  both fragments i and ii are also found at the Destination, indicating that the release of File A to Destination does not introduce new protected information. As a result, it does not require an alert. 
         [0129]    The example of  FIG. 15B , in contrast, finds that Destination  15010  contains only one of the two protected fragments, thus necessitating an alert. 
         [0130]      FIG. 16  presents one embodiment of this approach for monitoring and controlling information flow across workgroups. Each workgroup has a collection of files and an associated Document Evaluator  16020  that registers all workgroup file fragments. 
         [0131]    A central evaluator  16010  registers all protected files. 
         [0132]    In the example shown, a File A  16001  is under evaluation for delivery into a repository for workgroup k. Document Evaluator  16010  analyzes File A to detect any protected data fragments. The Overlap Comparer  16030  compares the results of  16010  to the Document Evaluator associated with workgroup k (labeled as  16020 - k ), and outputs the set of protected content fragments not already contained in (and thus not previously released to) workgroup k. 
         [0133]      FIG. 17  is a block diagram of a computer system as may be used to implement features of some embodiments of the disclosed technology. The computing system  1700  may be used to implement any of the entities, components or services depicted in the examples of  FIGS. 1-16  (and any other components described in this specification). The computing system  1700  may include one or more central processing units (“processors”)  1705 , memory  1710 , input/output devices  1725  (e.g., keyboard and pointing devices, display devices), storage devices  1720  (e.g., disk drives), and network adapters  1730  (e.g., network interfaces) that are connected to an interconnect  1715 . The interconnect  1715  is illustrated as an abstraction that represents any one or more separate physical buses, point to point connections, or both connected by appropriate bridges, adapters, or controllers. The interconnect  1715 , therefore, may include, for example, a system bus, a Peripheral Component Interconnect (PCI) bus or PCI-Express bus, a HyperTransport or industry standard architecture (ISA) bus, a small computer system interface (SCSI) bus, a universal serial bus (USB), IIC (I2C) bus, or an Institute of Electrical and Electronics Engineers (IEEE) standard 1394 bus, also called “Firewire”. 
         [0134]    The memory  1710  and storage devices  1720  are computer-readable storage media that may store instructions that implement at least portions of the described technology. In addition, the data structures and message structures may be stored or transmitted via a data transmission medium, such as a signal on a communications link. Various communications links may be used, such as the Internet, a local area network, a wide area network, or a point-to-point dial-up connection. Thus, computer readable media can include computer-readable storage media (e.g., “non-transitory” media) and computer-readable transmission media. 
         [0135]    The instructions stored in memory  1710  can be implemented as software and/or firmware to program the processor(s)  1705  to carry out actions described above. In some embodiments, such software or firmware may be initially provided to the computing system  1700  by downloading it from a remote system through the computing system  1700  (e.g., via network adapter  1730 ). 
       CONCLUSION 
       [0136]    The technology introduced herein can be implemented by, for example, programmable circuitry (e.g., one or more microprocessors) programmed with software and/or firmware, or entirely in special-purpose hardwired (non-programmable) circuitry, or in a combination of such forms. Special-purpose hardwired circuitry may be in the form of, for example, one or more ASICs, PLDs, FPGAs, etc. 
         [0137]    The systems corresponding to the methods explained above and associated embodiments relate to apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, and magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, or any type of media suitable for storing electronic instructions, each coupled to a computer system. 
         [0138]    The algorithms and software presented herein are not inherently related to any particular computer or other apparatus. Various general purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from other portions of this description. In addition, the present invention is not described with reference to any particular programming language, and various embodiments may thus be implemented using a variety of programming languages. 
         [0139]    In addition to the above mentioned examples, various other modifications and alterations of the invention may be made without departing from the invention. Accordingly, the described examples in the above disclosure are not to be considered as limiting. 
         [0140]    While this invention has been described in terms of several embodiments, there are alterations, modifications, permutations, and substitute equivalents, which fall within the scope of this invention. Although sub-section titles have been provided to aid in the description of the invention, these titles are merely illustrative and are not intended to limit the scope of the present invention. 
         [0141]    It should also be noted that there are many alternative ways of implementing the methods and apparatuses of the present invention. It is therefore intended that the following appended claims be interpreted as including all such alterations, modifications, permutations, and substitute equivalents as fall within the true spirit and scope of the present invention.