, 刘道胜 , 黄诚 四川大学 电子信息学院, 成都 610064
收稿日期：2016-12-14
作者简介：方勇(1966-), 男, 教授。E-mail:yfang@scu.edu.cn
摘要：互联网上充斥着大量恶意用户，而互联网服务提供商通常有海量的注册用户，使得系统难以从中发现虚假账户。针对海量注册数据中，恶意用户批量注册的虚假账户通常具有相似性的特点。该文提出海量数据中定位虚假账户的系统模型，利用用户名字符串组成模式对海量数据进行预分类，进而对每个分类中元素计算字符串相似度，即计算字符串Levenshtein距离。设置合适的阈值，进行层次聚类分析，从而定位藏匿在海量注册数据中的成组的虚假账户。实验结果表明：该系统模型有效，与现有的模型相比，该系统对数据维度、数据特性依赖较小。
关键词：数据安全虚假账户机器学习层次聚类
Detecting of fake accounts with hierarchical clustering
FANG Yong
, LIU Daosheng, HUANG ChengCollege of Electronics and Information Engineering, Sichuan University, Chengdu 610064, China
Abstract: Since there are many malicious users on the Internet, popular online websites sometimes have millions of registered users. The system cannot easily distinguish between fake accounts and legitimate users. Fake accounts registered by a single malicious user often have similar profiles. This paper presents a new framework to find fake accounts in large numbers of users. The framework uses username string patterns to classify the original data and then calculates the similarity as measured by the Levenshtein distance between any two elements in one category. Hierarchical clustering with a proper threshold then finds groups of fake accounts hidden in the large amount of registration data. Tests demonstrate the effectiveness of this framework which algorithm relies less on data dimensions and features than other algorithms.
Key words: data securityfake accountsmachine learninghierarchical clustering
在Web2.0时代，用户通过在线网站获取信息资源、交流分享。互联网改变了人们的生活。然而，有一些用户却通过滥用互联网服务获取不正当的利益。这些恶意用户通过发布垃圾信息、虚假信息、钓鱼信息等方式扰乱互联网秩序[1-3]。当部分服务商建立新网站或者推出新业务时，服务商会在网上进行一些促销返利活动以招揽顾客。恶意用户通过注册大量虚假账户直接获取经济利益。当这些Web服务提供商不再有促销活动时，这些虚假账户就变成了僵尸账户，网站需要对所有用户进行管理，无疑增大了网站运营成本。
这些网站也会采取一些安全措施来规避风险。例如举报机制，由于注册新用户几乎零成本，即使网站封停了一个恶意用户，该用户也可以马上注册新的身份实施攻击。并且恶意用户使用虚假信息注册用户时由于信息不具有真实性，定位用户的真实身份变得极为困难。有些网站则采用验证用户手机号或者邮箱的方式唯一标识一个真实用户，以防范攻击，然而恶意用户往往可以有大量的手机号和邮箱可以用于注册，这种防范措施也不能很好地抵抗攻击。
用户名是用户在一个网站上的身份标识。虽然部分网站开始启用手机验证、邮箱验证，将手机和邮箱以作为用户的唯一性身份标识，但是绝大多数网站仍然为用户设置用户名，作为用户在网络上的虚拟身份标识。就像每个人都有一个名字一样，用户需要为自己设置一个个性的用户名以彰显个性，从而在社交网络中脱颖而出。而恶意用户注册大量虚假账户时不可能采用人工注册的方式，而会编写恶意脚本去批量注册用户，为了方便管理，这些批量注册的用户往往会具有相似性。
在社交网络账户中检测虚假账户已经有一些研究，包括行为分析、机器学习等方法。Malhotra等[4]采用行为分析的方法研究了恶意用户发现技术，获取用户在不同网站上的注册信息形成用户数字指纹，发现那些在不同网站中注册虚假账户的恶意用户；Cao等[5]采用社交图谱的方式给用户评分，以辅助发现社交网络中的虚假账户；Cao等[6]采用随机森林、逻辑回归、支持向量机等机器学习方法，以LinkedIn的已标记的恶意账户集作为训练数据，去发现恶意用户；Fire等[7]采用决策树、朴素Bayes分类的方法去识别恶意用户；Jin等[8]则分析了账户克隆攻击的特征并形成一个攻击检测模型。现有的研究很多都采用基于账户活动特征或者账户克隆攻击发生时的一些特征去发现恶意用户。在采用机器学习检测恶意用户时需要一些样本数据以供训练，往往需要大量用户特征数据。
近年来，互联网用户信息泄露事件时有发生，有数亿的用户数据可以在网上下载到，包括境内的CSDN、天涯(Tianya)、7k7k等[9]和境外的Hotmail、Yahoo等[10]的用户数据，这些数据为本文的研究提供了丰富的样本数据。本文提出大数据集环境下虚假账户发现技术。通过对数据进行预分类，并结合层次聚类的方法进行虚假账户检测。通过实验证明该方法能够有效定位大数据集下的虚假账户，为海量数据下定位虚假账户提供了有效的解决方案。
1 系统模型本文提出的系统总体架构如图 1所示，系统主要包括2个大的模块：数据预分类和聚类分析。系统支持离线和实时检测。一般一个网站的所有用户数据都存储在数据库中，预分类模块从数据库中读取用户唯一性标识，将其按字符组成成分(汉字、大写字母、小写字母、数字、符号)标识成字符模式，然后将这些字符模式存储到另一个数据表中，以保证原始数据完整性。系统将按不同字符模式对原始用户数据进行分组供后续聚类分析。
 |
| 图 1 基于层次聚类的虚假用户检测系统 |
| 图选项 |
聚类模块对每一个字符模式类型进行基于字符串相似度聚类。此处共涉及2个阈值：字符串编辑距离、结果集元素个数。根据聚类结果，系统过滤掉聚类结果中集合元素数量较少的集合。在海量用户环境下，出现2个或者3个账户相似的概率很大，系统较难区分其是否是恶意用户。此时，系统输出结果即为获取到的虚假用户集，用户可以对虚假用户数据集的聚类效果进行判断。通过调整聚类相关参数，系统可以获得更好的聚类效果，最终可以标记出系统中的大量虚假用户。
2 基于文本相似度的聚类方法用户名作为网络上一个个体的身份标识，其组成具有非常大的随机性，组成成分包括汉字、大写字母、小写字母、数字和各种符号。而通常一些大型网站用户量巨大，在已知的一些研究中并没有发现能够从大量数据中提取虚假用户的方法。
通过对海量用户注册数据表的观察发现，通常用户名的注册都具有一定的规律，例如用户名组成可能为纯字母、字母和数字、字母和符号等。根据不同网站注册用户时的策略不同，会有汉字、大写字母、小写字母、数字、符号之间的各种组合。根据对注册数据的简单查询分析，同一个人一般都会有相似的用户名注册习惯，并且当同一个人注册多个虚假用户身份时，用户名、密码等注册资料通常都具有很强的相似性。有些专门做黑色产业的人甚至会使用注册机批量注册用户，虽然现在有验证码、短信验证、邮箱验证等技术来验证机器注册。但是还是有很多方法可以绕过这些防护手段来批量注册用户。通过对这些注册数据研究发现，程序批量注册的用户数据都有极大的相似性，例如用户名都是name001、name002、…、name010等。
为了发现海量数据中用户信息数据表中的规律，本文将这些庞大的数据集拆分成机器容易处理的小数据集，即对数据进行分类。
2.1 海量数据分类对海量数据进行分类的目的是提高下一步聚类的效率。有些网站可以使用用户名登录，有些网站则可以使用手机号或者邮箱登录。手机号或者邮箱通常都是唯一的，较容易验证。然而有些网站在使用手机号或者邮箱登录时仍然会提醒用户设置一个用户名，这是因为在社交网络中，使用手机号或邮箱去标识一个用户显得非常不友好，在这种方式下手机号和邮箱仍是用户的唯一性标识，用户名只是一个昵称，因此很多用户就会使用相同的用户名，此时再根据用户名分类，并不能获得最佳的分类效果。因此，针对不同的情况，本文提出以下方案：
1) 当存在用户名为唯一性标识时则按照用户名进行分类；
2) 当仅采用邮箱作为唯一性标识时，本文首先按邮箱类型做一次分类后再将邮箱用户名按方案1中用户名分类方案进行分类；
3) 当仅采用手机号作为唯一性标识时，本文将采用手机号前七位来判别其归属地信息，因为如果恶意用户批量购买手机号去注册虚假账号时就会有相同的归属地标识。但并不是每一个虚假账号都会批量购买手机号，因此该方案并不通用。该方案也可以不分类，分类只是为了提高下一步中的聚类效率，并不会影响结果。
用户名的分类算法逐个字符地将字符串转换成字符串模式，即将所有汉字替换成H、所有大写字母替换成U、小写字母替换成L、数字替换成N，其他各种符号替换成O，然后系统将每一个字符串表示成能标识其组成的字符串模式，例如用户名：“你好abc123”会被表示成HHLLLNNN，而“你好aaa456”也会被标识成HHLLLNNN，这样相同的字符串模式的字符将获得相同的表示。字符串模式识别算法如图 2所示。
 |
| 图 2 字符串模式识别算法 |
| 图选项 |
系统将字符串转换成其字符串模式后将其存储到数据库中，随后系统使用数据库查询语句统计每一种模式的数量。其中Tianya用户数据中排名前五的用户名字符模式如表 1所示。
表 1 Tianya用户名字符模式TOP5
| 序号 | 用户名字符模式 | 比例/% |
| 1 | HHHH | 10.6 |
| 2 | HHHHH | 5.6 |
| 3 | HHH | 5.4 |
| 4 | LLLLLL | 3.0 |
| 5 | LLLLLLLL | 2.9 |
表选项
系统采用数据表的联合查询获取特定模式的所有数据集。通过对排名前五的用户名字符模式研究，发现HHHH多为成语或者4个字的词语，HHHHH也为5个字的词句。而HHH多为1个词或者1个人名。天涯论坛是一个文学类论坛，允许用户使用汉字作为用户名，排名前三的用户名模式都由汉字组成，汉字中一些3字、4字、5字的词语多能代表其情怀。LLLLLL和LLLLLLLL则是英文小写的用户名。
对海量数据进行分类之后，系统可以获得多个分类的小数据集，随后按照每个数据集数据量的大小进行过滤，设定阈值K，当集合元素个数少于K时，将所有数据量较少的集合合并成一个集合。下面系统将对这些分类逐个进行聚类分析，发现其中的虚假账户集。
2.2 分类数据聚类2.2.1 层次聚类算法层次聚类算法主要包括自下而上和自顶而下的聚类方法2种，其中自下而上的聚类方法一开始将每个数据点各自归为一个类别，每次迭代选取距离最近的2个类别并进行合并，直到最后只剩一个类别为止。通常系统会预设一个阈值，当最近的2个类之间的距离大于这个阈值时则停止聚类。而自顶而下的聚类方法则是一开始将所有的样本都归为一类，然后逐步将其划分为更小的单元，直到最后每一个样本都成为一类，在迭代过程中需要确定一个阈值，当每个集合的松散度低于这个阈值则划分终止。
本文主要采用自下而上的层次聚类方法，在计算2个类之间的相似度时也有多种方法：Single Linkage采用2个集合中最近的2个元素的距离作为2个集合的距离；Complete Linkage采用2个集合中最远的2个元素的距离作为2个集合的距离；Group Average则求2个集合中元素距离的平均值作为集合的距离。
聚类过程中需要计算字符串的相似度，采用2个集合中的最近的元素的距离作为2个集合的距离。综合分析这样会得到更好的聚类效果。
例如，存在字符串abc123d、abc123e、abc124d，其中abc123d和abc123e的编辑距离为1；abc124d和abc123d的距离为1；abc124d和abc123e的距离为2；当设置距离的阈值为1时，首先abc123d和abc123e将聚成一类，abc124d根据Complete Linkage和Group Average都不会聚成一类，而明显abc124d和abc123d距离为1，这3个字符串应该聚成一类。Single Linkage在数据集较大时会使得一个数据集中2个元素的编辑距离相差较远。但本文编辑距离的阈值设置比较小，一般在3以内，2个字符的最大差距也不会大于6，这些数据集中的元素总是相互间联系紧密的，因此聚类结果仍较为理想。
层次聚类的步骤如下：
步骤1??初始化过程。获取特征数据列，从数据表中的获取数据集Mi, i=1, 2, …, k, 确定哪些列可以作为特征数据列以计算相似度，将每个数据集都视为一个集合。
步骤2??基于字符串相似性计算数据集间的相似度。本文定义字符串的相似度为S(A, B)，通过计算每个集合间的相似度并把相似度最高的2个集合合并。
步骤3??重新计算新的集合间的相似度。
步骤4??重复步骤2和3直至相似度最小值达到阈值。
步骤5??过滤所有集合，取出集合中元素个数满足阈值K2的集合作为最终的虚假账户集合，并作可视化展示。
上述算法有其优点，即相似度最高的元素会优先聚合。最终得到一个树状结构，树结构越向下部分元素间相似度较高，树结构越向上相似度越低，在实际测试中，本文发现字符串相似度计算需要大量的时间开销。因此，本文改进了上述层次聚类算法。本文只关心字符串间的相似度是否满足阈值限制，则在步骤2中不需要计算集合间元素的最小相似度，只需要在2个集合间相似度满足阈值时，直接将2个集合合并，这样可以直接减少算法时间开销，可将时间复杂度降至最低O(n2)。
2.2.2 基于编辑距离的相似度计算本文通过编辑距离衡量字符串间相似度。假设字符串Mi和Mj分别由{C1，C2，…, Ci}和{D1，D2，…, Dj}组成。假设通过修改、添加、删除一个或者多个Mi中元素，可以将Mi变成Mj，则所需要的编辑次数即为编辑距离。计算Mi和Mj之间的相似度等同于计算Mi和Mj的编辑距离。
通常，本文将获取每条记录邮箱、用户名、密码等多个字段的相似度的均值。此时本文定义字符串A与B相似度为
| $S\left( {A,B} \right) = 1 - \frac{{{\text{Levenshtein}}\left( {A,B} \right)}}{{{\text{Max}}({\text{Len}}\left( A \right),{\text{Len}}\left( B \right))}}.$ |
当只采用一个字段进行距离计算时，本文将直接基于每条记录的用户名字符串计算相似度，则字符串A与B之间的相似度可简化为
| $S\left( {A, {\rm{ }}B} \right) = {\rm{Levenshtein}}\left( {A, {\rm{ }}B} \right).$ |
3 实验结果本文提出基于层次聚类的新型恶意用户检测技术，采用天涯网站用户数据作为样本数据，样本数据总计30 605 144条，天涯是华人的大用户网络平台，涉及社交媒体、社区游戏、社区型电子商务等多方位内容。该网络平台也存在恶意用户注册虚假账户进行恶意操作的现象。天涯社区在2009年遭到入侵，导致数据库泄露。本文从网络公开渠道获取泄露的用户数据，并致力于发现天涯论坛中早期存在的恶意用户。本文首先将其按字符串模式进行分类，共得到分类数113 104个，其中分类元素个数大于100的有3 783个，随机选取一些分类对其进行聚类分析，以发现虚假账户集，部分分类的结果如表 2所示。
表 2 实验结果
| 序号 | 用户名字符模式 | 总数 | 虚假用户数 | 虚假用户集合 | 虚假用户比例/% |
| 1 | LNLLNLLNL | 102 | 26 | 3 | 25.49 |
| 2 | NNNNNNNNNNNL | 390 | 48 | 9 | 12.31 |
| 3 | LLLLLLLLLU | 440 | 16 | 6 | 3.64 |
| 4 | NNLLLLLLLLL | 979 | 31 | 10 | 3.17 |
| 5 | LLNNNNNNNNNN | 7 573 | 465 | 90 | 6.14 |
| 6 | LLLLLNNNNNNNNN | 8 944 | 208 | 25 | 2.33 |
表选项
通过对各个字符串模式聚类结果的分析，本文选取模式为LLLLLNNNNNNNNN的一个虚假账户集的部分结果，如表 3所示。该恶意账户集总计包含35个虚假账号，其中ID号为2595209的账户注册较早，其余账户采用相同的密码，相似的邮箱，近乎连续的ID号。
表 3 字符串模式LLLLLNNNNNNNNN部分结果
| ID | 用户名 | 密码 | 邮箱 |
| 2595209 | feiyu888111001 | yu04551 | 445429424@qq.com |
| 9442782 | feiyu888111002 | yu04551 | feiyu888111002@163.com |
| 9442784 | feiyu888111004 | yu04551 | feiyu888111004@163.com |
| 9442791 | feiyu888111010 | yu04551 | feiyu888111010@yahoo.cn |
表选项
上述实验只采用用户名作为判决因子，同时通过判断E-mail或密码的相似度，以判断聚类效果。在实验中发现，如果增大聚类中字符串编辑距离的阈值，可以获得更多可能的虚假账户集，但是误报率也将增加。同时，通过设定数据集过滤的阈值，将小集合过滤掉，在对特大数据集进行聚类时，结果集中的小数据集是虚假账户集的概率较低。而设定较小的过滤阈值将有助于发现社交网络中的关联账户，即发现普通网名所使用的“小号”。在实际应用中可根据需求决定阈值大小，不同的参数会显著影响误报率。通过调节相关参数，辅助用户反馈，该方法可有效帮助用户发现虚假账户，因此系统误报率并不是考察系统性能的必要参数。实验结果也证明该方法可以发现藏匿在虚假账户后面的恶意用户的真实用户信息。定位恶意用户真实信息可有效打击互联网违规、违法行为。
4 结论通过对网上泄露的大量数据库的研究，本文设计了基于层次聚类的虚假账户检测技术。系统将海量用户注册数据按照字符串模式进行分类以优化聚类效果，通过将每个分类按照字符串编辑距离进行聚类，最终发现藏匿在海量用户数据下的恶意用户集，并证明该方法有一定概率定位恶意用户真实信息。该方法弥补了现有研究的不足，避免人工收集大量训练样本，也无需用户网络行为数据。实验证明该方法可以有效发现网站大量用户中的虚假账户，打击网络违法违规行为。
在研究过程中发现字符串相似度计算需要大量的计算时间开销，于是将所有的数据集进行分类以提高聚类速度。在下一步的研究中，将尝试采用Hadoop等技术进行分布式计算，减少聚类时间。另外本文将进一步研究机器学习算法，尝试找到计算代价更小的方法，更有效地在大数据集中发现恶意用户。
参考文献
| [1] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Wang A H. Don't follow me:Spam detection in twitter[C]//Security and Cryptography (SECRYPT), Proceedings of the 2010 International Conference. Athens, Greece:IEEE Press, 2010:1-10. |
| [2] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Mohammad R M, Thabtah F, McCluskey L. Intelligent rule-based phishing websites classification[J]. IET Information Security, 2014, 8(3): 153–160. DOI:10.1049/iet-ifs.2013.0202 |
| [3] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Marchal S, Saari K, Singh N, et al. Know your phish:Novel techniques for detecting phishing sites and their targets[C]//Distributed Computing Systems (ICDCS), 2016 IEEE 36th International Conference. Piscataway, NJ, USA:IEEE Press, 2016:323-333. |
| [4] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Malhotra A, Totti L, Meira Jr W, et al. Studying user footprints in different online social networks[C]//Advances in Social Networks Analysis and Mining (ASONAM), 2012 IEEE/ACM International Conference. Piscataway, NJ, USA:IEEE Press, 2012:1065-1070. |
| [5] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Cao Q, Sirivianos M, Yang X W, et al. Aiding the detection of fake accounts in large scale social online services[C]//Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. San Diego, CA, USA:USENIX Association, 2012:15-15. |
| [6] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Cao X, Freeman D M, Hwa T. Detecting clusters of fake accounts in online social networks[C]//Proceedings of the 8th ACM Workshop on Artificial Intelligence and Security. Denver, CO, USA:ACM Press, 2015:91-101. |
| [7] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Fire M, Katz G, Elovici Y. Strangers intrusion detection-detecting spammers and fake profiles in social networks based on topology anomalies[J]. Human Journal, 2012, 1(1): 26–39. |
| [8] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Jin L, Takabi H, Joshi J B D. Towards active detection of identity clone attacks on online social networks[C]//Proceedings of the first ACM conference on Data and application security and privacy. San Antonio, TX, USA:ACM, 2011:27-38. |
| [9] | Journal of Central South University(Science and Technology), 41(2):649-654.--> CHENG Yang, QI Zhao. How to set and manage your network password:A multidimensional scheme of password reuse[C]//Conference on e-Business, e-Services and e-Society. Berlin:Springer, 2014:264-276. |
| [10] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Das A, Bonneau J, Caesar M, et al. The tangled web of password reuse[C]//Network and Distributed System Security Symposium. San Diego, CA, USA:The Internet Society, 2014:23-26. |
| [11] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Yang C, Hung J, Lin ZX. An analysis view on password patterns of Chinese Internet users[J]. Nankai Business Review International, 2013, 4(1): 66–77. DOI:10.1108/20408741311303887 |
| [12] | Journal of Central South University(Science and Technology), 41(2):649-654.--> LI Zhigong, HAN Weili, XU Wenyuan. A large-scale empirical analysis of Chinese Web passwords[C]//The 23rd USENIX Conference on Security Symposium. San Diego, CA, USA:USENIX Security, 2014:559-574. |
