通过确定性自然数据的替换扰乱数据结构的方法和系统

摘要

一种从被扰乱的数据结果创建数据结构的方法和系统。首先，该系统对期望被扰乱的第一数据结构进行操作，并且基于第一数据结构的一部分生成一数据串。接下来就基于该数据串，从第三数据结构确定性地生成第二数据结构，并且用第二数据结构代替第一数据结构。

权利要求

1.一种数据扰乱的方法，包括：

基于期望其扰乱的源数据结构的一部分创建数据串，包括确定所述源数据结构的所述部分的标识符并对该标识符应用确定性函数，所述数据串是所述确定性函数的输出，其中所述源数据结构包括一行或多行以及一列或多列的数据值；

为所述数据串的各部分分配包括在所述源数据结构中的一个或多个数据字段类型；

基于所述数据串，从至少一个参考数据结构中确定性地生成合成数据结构的相应的一部分，(1)其中所述合成数据结构和所述至少一个参考数据结构包括一行或多行以及一列或多列的数据值，并且(2)在所述合成数据结构和所述至少一个参考数据结构的一列或多列中的每一列都对应于在所述源数据结构中的所述一列或多列的数据值的类型；以及用所述合成数据结构代替所述源数据结构。

2.如权利要求1所述的方法，其特征在于，所述源数据结构包括用于所述一行或多行数据值的每一行的标识符。

3.如权利要求2所述的方法，其特征在于，还包括：把加权值分配给所述源数据结构的所述一行或多行的每一行中的各个类型的数据值；

以及

基于所述源数据结构的所述分配的加权值，将来自所述至少一个参考数据结构的数据值装入所述合成数据结构。

4.如权利要求3所述的方法，其特征在于，分配加权值还包括根据在所述源数据结构的所述一行或多行的每一行中的所述类型的数据值的总体中的出现来分配加权值，使得在所述合成数据结构内相应的数据值与实际总体中所找出的自然模式相匹配。

5.如权利要求4所述的方法，其特征在于，还包括：把所述数据串的一部分分配给所述一个或多个数据字段类型的每一个；以及基于所述部分和相应的加权值，在所述至少一个参考数据结构内定位所装入的数据值。

6.如权利要求5所述的方法，其特征在于，所述数据字段类型对应于名和姓、公司名、性别、种族、支付方法、薪水和年龄。

说明书

通过确定性自然数据的替换扰乱数据结构的方法和系统

[0001] 本发明专利申请是申请日为2006年1月6日、申请号为200610002518.4、名称为“通过确定性自然数据的替换扰乱数据结构的方法和系统”的发明专利申请的分案申请。

技术领域

[0002] 本发明的实施例涉及数据结构扰乱的领域。更具体但非限制地，本发明的实施例提供一种新的和有用的方法和系统，用于使用反映了在数据结构中数据值分配的被确定性生成的伪随机数据值来代替该数据结构中的数据值。

背景技术

[0003] 许多公司都维持有包括了客户或雇员信息的数据库。所述信息可包括姓名、地址、电话号码、社会保险号码、公司名称、薪水和购买历史。例如一家互联网销售公司可以具有包括了客户姓名、电话号码、支付方法和购买历史的客户数据库。在另一个实施例中，财会部分可具有关于其雇员的薪水信息。由于这些信息中诸如支付方法、社会保险号码和薪水等信息的敏感性，对这些信息的访问只限于公司内相对较小的一组人。

[0004] 正如软件应用中所普遍的，要求由计算机程序员进行故障诊断就会引发一些问题。当在具有敏感信息的数据库上运行的软件应用程序发生故障时，程序员为了故障诊断需要访问所述敏感数据库。这就导致了敏感信息被通常对该信息不具有访问权限的人看到。例如在薪水发放的实例中，薪水信息的传播会在公司内引发关于薪水差异的内部矛盾。在互联网销售的实例中，支付方法和诸如社会保险号码的其他个人信息的传播会导致身份盗用。然而为了有效地调试故障软件应用程序，程序员需要访问实际数据，尤其要访问实际数据的分配(地理分配、姓名分配等等)。

[0005] 本领域内已知可通过随机数据替代扰乱数据库，从而生成了测试数据库。然而随机数据替代不会产生在自然数据库内找到的实际数据分配。所以就需要一种方法和系统来扰乱至少部分数据库以产生测试数据库，该测试数据库具有反映了在实际数据库中找到的分配的数据分配。

发明内容

[0006] 本发明的实施例提供了一种通过由确定性的自然数据替代的代替来扰乱数据的方法。此外，本发明的实施例在所述技术领域内可具有若干实际应用，包括但不限于使用外观自然的数据确定性地代替机密数据。这些数据反映了就数据分布而言在原始数据中找到的模式，但不包括原始的机密数据。

[0007] 在一个实施例中，提供一种用于扰乱数据的方法。所述方法包括对期望扰乱的第一数据结构进行操作并且基于所述第一数据结构的一部分生成数据串。基于所述数据串，就从第三数据结构中确定性地生成第二数据结构并且所述第二数据结构代替所述第一数据结构。

[0008] 在另一个实施例中，提供一种用于构造测试数据结构的方法。所述方法包括影响具有若干数据字段类型的源数据结构，其中每个数据字段都包括若干行数据并且所述方法还确定用于每行数据的标识符。接下来所述方法对于每行数据，基于所述标识符生成数据串，把该数据串的一部分映射到参考数据结构内的值并且把所述参考数据结构内的映射值装入测试数据结构。

[0009] 在又一个实施例中，提供一种计算机可读介质，所述介质具有用于执行生成合成数据结构的方法的计算机可用指令。所述方法包括首先提供一种参考数据结构和一种源数据结构，其中每个数据结构都具有若干数据字段类型并且每个数据字段类型都包括若干行数据值。接下来，所述方法包括根据预定的模式为所述源数据结构中的每行数据值分配加权值并且为所述源数据结构的每行数据值分别导出数据串。为了所述源数据结构的每行数据值，在所述数据值行内的每个数据值都基于所述加权值、各自的数据串以及数据字段类型，被映射到所述参考数据结构内数据值行中的数据值上。最后，用所述参考数据结构的映射值装入所述合成的数据结构。

[0010] 另外的特性将在如下详细讨论。

附图说明

[0011] 如下将参考附图详述本发明的实施例，结合在此作为参考的附图包括：

[0012] 图1A是示出了一个典型定购过程的系统框图；

[0013] 图1B是示出了用于扰乱数据结构的方法的一个实施例的流程图；

[0014] 图2是详细示出了用于生成数据串的过程的一个实施例的流程图；

[0015] 图3是一个典型的数据串；

[0016] 图4是一个期望被扰乱的典型数据结构；

[0017] 图5是详细示出了用于扰乱数据结构的过程的一个实施例的流程图；

[0018] 图6是从图4的数据结构中导出的典型的被扰乱的数据结构；

[0019] 图7是详细示出了用于扰乱数据结构的过程的另一个实施例的流程图；

[0020] 图8是示出了分配有加权值的各种数据字段类型的示意图。

具体实施方式

[0021] 本发明的实施例提供了一种新颖的方法和系统，它们通过为在所述第一数据结构内的每行数据值确定性地生成唯一的数据串，使用所述数据串将所述第一数据结构的所述行中的每个数据映射给参考数据结构的数据值并且基于在所述参考数据结构中的映射数据值来创建第二数据结构，来扰乱第一数据结构内的数据值。确定性的方法和系统能够实现可再现的结果使得对于第一数据结构扰乱的每个实例，第一数据结构中的一行数据值都能够与第二数据结构中的一行数据值相关。

[0022] 此外，在本发明各个实施例中示出的新颖方法和系统在某些实施例中可以将加权值分配给所述第一数据结构内特定类型的数据值用于创建大致近似于第一数据结构内数据值分配的第二数据结构。这样，随机出现的所述第二数据结构就在对所述第一数据结构进行操作的软件应用程序的测试和故障诊断中十分有效。

[0023] 从随后通过的详细描述和本发明各个实施例的附图中将更好地理解本发明的实施例。尽管如此，不应将详细描述和附图理解为将本发明限制在某些特定实施例上。相反地，提供这些特定的实施例是出于帮助更好的理解本发明的示意性目的。

[0024] 阐述了特定的硬件设备、编程语言、组件、程序以及包括操作环境等等的多种细节用于提供对本发明的透彻理解。在其他实例中，结构、设备和程序以框图而非细节的形式示出以避免模糊本发明的实施例。但是本领域普通技术人员应该理解没有这些特定细节也可实现本发明的实施例。计算机系统、服务器、工作站和其他机器可以通过例如包括一个或多个网络的通信介质相互连接。此外示出用于解释本发明各个实施例的数据结构可以是但不限于数据库、电子表格以及其他能够作为存储介质的装置。

[0025] 现在转到图1A，示出的是使用在图1B到图8中详细描述的数据扰乱方法的典型定购系统的过程10的系统框图。过程10在客户服务代理接收到客户定单的步骤14处开始。可以通过电子商务网站、电话或个人收到所述定单。在步骤16处，过程10从包括了客户数据结构12A和库存可用性数据结构12B的数据结构12中检索用户数据。客户数据结构12A可以包括转入地址、电话、公司社会保险号码以及该客户过去的支付方法的客户信息。在步骤18处，过程10基于来自库存数据结构12B的可用库存以及来自客户数据结构12A的出货信息生成一张发票。

[0026] 在步骤20处，出货给所述客户的定单是基于在步骤18处生成的发票。在步骤22处，如果客户正当地收到该定单就完成了所述过程。然而，如果该定单未被恰当地接收(诸如在定单出货错误或者合适的定单被送给错误的顾客的情况下)，就必须调试过程10中使用的软件应用程序以用于确定故障的根源。在步骤24处，使用来自客户数据结构12A和库存数据结构12B的测试数据值生成数据结构13。随后就在步骤26处使用测试数据结构13分析过程10使用的软件应用程序。通常期望包括在客户数据结构12A内的敏感信息不要被分发到要求访问数据结构12A内信息的这些有限的一组人之外的地方。通过使用确定性的方法扰乱数据结构12A内的数据，就可生成带有外表自然并且保护客户机密信息的测试数据结构13。
因为使用确定性的函数生成测试数据结构13内的数据值，所以在测试数据结构13内的数据录入项可被追溯到数据结构12A内的数据值从而定位过程10使用的所述软件应用程序内的问题根源。

[0027] 转向图1B，示出的是用于从期望被扰乱的第一或源数据结构中生成测试或第二数据结构的方法100的一个实施例。图4示出了具有列410-420和行422-432的典型数据结构400。数据结构400包括数据字段类型的各个列。在典型的数据结构400中，提供的列是用于指示每行的ID号码。包括在数据结构400内的各种数据字段类型包括名、姓、公司、性别和电话号码。在某些实施例中的数据结构400还可包括诸如年龄和种族的其他数据字段类型。

[0028] 现在回到图1B，所述扰乱方法100包括了为期望扰乱的数据结构行生成数据串的步骤110。例如数据结构400的行422包括被操作用于生成数据串的ID号码“0001”。在步骤110处生成数据串的过程还参考了图2进行讨论。继续扰乱方法100，在步骤112处，确定诸如数据结构400内的地址或姓名字段数据值的第一数据字段类型。例如，在行422中的数据值“Chris”是由列412指定的“名”数据字段类型。在步骤114处，检索行422和列412处的数据值“Chris”。在步骤116处，基于数据类型和使用第三或一个或多个参考数据结构(未示出)的数据串来扰乱数据值“Chris”并创建相应的测试数据结构。所述测试数据结构包括对应于数据值“Chris”的来自参考数据结构的被扰乱数据值。在步骤118中，如果期望被扰乱的所述数据结构中存在更多列，诸如数据结构400的“姓”列414、“公司”列416、“性别”列418和“电话号码”列420，那么随后就重复步骤112到116。在每列都被扰乱之后，在步骤120处方法
100移动到下一行。例如数据结构400的行424。如果存在更多的行，就在步骤110处生成数据串并且方法100重复步骤112至118。当期望被扰乱的数据结构中没有行存在时，就完成方法
100。诸如图1A中测试数据结构13的第二或测试数据结构已经被创建，并且在所述源数据结构内的机密数据也已被扰乱。

[0029] 现在转到图2，示出的是用于生成图1B步骤110的数据串的详细过程。步骤110的过程包括确定所述源数据结构内行数据值的标识符的步骤110A。在数据结构400中，“ID”列410可用作标识符。在行422内的标识符可以是“0001”。在步骤110B处，将标识符应用到确定性的函数。确定性的函数的一个实例是MD-5(报文摘要算法5)加密算法。MD-5是一种广泛使用的带有128位散列输出值的密码散列函数。使用MD-5函数，即使输入消息内很小的变化也能导致完全不同的输出消息或散列值。所述MD-5算法还在因特网工程特别任务(IETF)请求评论(R.F.C.)1321中描述，该文结合在此作为参考。在此使用的所述MD-5确定性的算法仅用作示意性的目的。本发明的各个实施例也可使用其他确定性的函数，诸如但不限于SHA-1和RIPEMD-160。

[0030] 继续参考图2，在步骤110C处，所述数据串的部分或所述确定性函数的输出被分配给所述源数据结构内的数据字段类型。图4的数据结构400包括若干数据字段类型，即“ID”410、“名”412、“姓”414、“公司”416、“性别”418以及“电话号码”420。参见图3，示出的是一个典型的一般数据串300。数据串300包括与数据结构400的五个数据字段类型相匹配的五个部分、在步骤110C的一个实施例中，数据串300的一个部分312可分配给包括由“名”数据字段类型的数据结构400的列412而数据串300的一个部分314可分配给包括由“姓”数据字段类型的数据结构400的列414。类似地，部分316可分配给列416、部分318可分配给列418而部分320可分配给数据结构400的列420、虽然在此实施例中数据串300的各部分被以分块方式分配给数据结构400内的数据字段类型，但是在本发明的其他实施例，数据串300的各部分能够以不连续组的形式被分配给数据结构400内的各个数据字段类型的列。

[0031] 现在转到图5，示出的是用于扰乱在图1B的步骤116中讨论的源数据结构数据值的详细过程。在步骤116A处，检索在图1B的步骤110处生成并在图2中被进一步解释的数据串的部分。出于示意性的目的，在步骤116A处检索图3的数据串300。在步骤116B处，对应于例如在数据结构400的数据字段类型的数据串300的一部分被映射给对应于在参考结构(未示出)中数据字段类型的数据值。所述参考数据结构例如可以是包括了姓/名、地址、性别、年龄、电话号码、社会保险号码和种族的普查资料。此外在本发明的其他实施例中，所述参考数据结构可以是单数据结构或者是数据结构的编译，它们都包括对应于数据字段类型的数据值。在步骤116C处，检索在参考数据结构内的映射数据值以创建合成或测试数据结构。一典型的合成数据结构由图6中的数据结构300示出。合成的数据结构600包括与图4中的源或被扰乱数据结构400相同的列号和数据类型并且包括与图4中数据结构400大致类似的数据。

[0032] 对每一实例都使用所述确定性函数，使得来自源数据结构的一行数据值被映射至参考数据结构以生成合成数据内的一行数据值。在源数据结构内给定的一行数据值和在合成数据结构内相应的被扰乱的一行数据值之间存在这可再生的关系。换句话说，参考图4和图6，对于源数据结构400的每一扰乱，图4的行422都对应于图6的行622。如前关于图1A的描述，这一可再生的能力使得能够多次调试在定单和出货过程中使用的软件应用程序而不丢失在客户数据结构12A和测试数据结构13的数据值之间的关系。

[0033] 如前所述，图3中数据串300的一部分被用于将数据结构400中的一个值映射至参考数据结构(未示出)的一个值。例如，年龄数据类型可以对应于数据串300的第22至27位，而姓和名可以使用数据串300的11位最低有效位。在选择姓和名的实例中，可从普查统计局下载美国最流行的65000个姓和名。为了从普查统计局列出的65000个中选出一个姓和名，就需要来自数据串300的特定的位数。例如，可从数据串300中选择16个独立位并组合到一起用作姓，而从数据串300中选择另外12位组合到一起用作名。虽然在此实例中选择了12和16位，但是也可选择其他的位数。例如，如果用于名的二进制位数合计达二，则就选择参考数据结构内的第二输入项。随后就把从列出的65000个姓和名中选出的姓和名插入合成的数据库结构500。类似地，当使用地址时，数据串300的一部分就用于选择一个地址。例如，如果选作地址的数据串300的部分合计达192，则在地址参考数据库中的第192个输入项就被选择并插入图6中的合成数据结构600。

[0034] 现在参考图7，示出的是用于扰乱在图1B的步骤116中描述的源数据结构的数据值的另一个实施例。在步骤116D处，为特定的数据类型分配加权值。例如，以字母“m”开头的公司名出现的频率要高于以字母“z”开头的公司名。则加权算法可连同确定性的函数一起被用于模拟总体中公司名的实际分布。结合参见图4和图6，在数据结构400的“公司”数据类型字段中以字母“m”开头的公司出现的频率要高于以字母“z”开头的公司。类似地，在图6中数据结构600的“公司”数据类型字段中，名字以字母“m”开头的公司和名字以字母“z”开头的公司的出现频率也与上述相同或类似。如图8所示，将给予其他的数据字段类型类似的加权值。加权值814可被分配给性别810、年龄812、姓和名816以及种族818。

[0035] 再次参见图7，方法116在步骤116E处继续，其中检索数据串300的一部分并在步骤116F处将其映射给参考数据结构中的值。随后在步骤116G处，就利用来自参考数据结构的映射值生成合成数据结构。虽然在一个实施例中的参考数据结构可以包括了包含在期望被扰乱的数据结构内的所有数据值和数据类型，但是其他实施例可以包括若干参考数据结构，各自用于包含在期望被扰乱的数据结构内的每一数据类型。

[0036] 本发明的某些实施例可利用加权算法来精确再现总体中的数据类型分布。对加权算法的使用依赖于在参考数据结构内被扰乱数据的期望精确度或者所述分布的精确度。

[0037] 已参考特定的实施例描述了本发明，这些实施例仅出于示意性而非限制性的目的。本领域普通技术人员显而易见的是可选实施例没有背离本发明的范围。由于本发明的特性使得许多可选实施例存在但未包括在本说明中。熟练的程序员可以开发用于实现前述改进的可选方法而不背离本发明的范围。应该理解的是可以不参考其他的特性和子组合而利用特定的特性和子组合并仍被认为位于本权利要求的范围之内。在各附图中列出的步骤不必以特定的次序描述。前述流程图中的步骤并非都是必须的步骤。