基于社会认证的网络身份模型＊

邵成成，姜新文，陈 侃，朱培栋

（国防科学技术大学计算机学院，湖南 长沙410073）

1 引言

在线社会网络OSN（Online Social Network）近年来得到飞速发展。据Statistic Brain统计，Facebook注册用户已超过10 亿，Twitter注册用户已达到500万；QQ 的统计表明，中国区最高同时在线人数超1.7亿。

OSN 在给人们生活带来便利的同时，其匿名性却导致水军泛滥、谣言传播、隐私侵犯等一系列问题。如淘宝上的恶意刷评、谣言所致的群体事件、人肉搜索事件等。为解决OSN 的匿名性，有人提出网络实名制。网络实名制是指将网络用户的身份与其个人真实身份建立一一对应关系的网络管理制度，实质是将现实社会中的身份标识引入网络，使得每一个“网络人”都能和“现实人”对应起来。韩国作为世界第一个全面实行实名制的国家，虽因实名信息的泄漏而中止，但有很多学者对其进行了研究。Song D H 等人［1］重新评估韩国政府针对“烛光游行”采取的监管措施所带来的影响，反映出网络实名制在言论自由上的严重障碍。而Cho D 等人［2，3］的数据分析表明，实名制对用户的行为总的来看是积极的，明显减少用户不受约束的行为。Oh Y 等人［4］的分析表明，实名制易致用户信息泄露并受钓鱼网站威胁。

网络实名制作为身份认证手段，依赖实名信息将“现实人”与“网络人”联系起来。要从根本上解决实名信息泄漏的问题，需要改变身份认证时所需要的依赖因素——不能依赖实名信息作为认证因素。

在计算机领域，传统的身份认证因素主要依赖用户名/密码、第三方凭证和生物特征。这些因素都不太适OSN 上的舆论监管。RSA 实验室的Brainard J 等 人［5］提 出 第 四 种 可 以 依 赖 的 因素——somebody you know，即依赖于社会关系。在此基础上，Microsoft Research Lab的Schechter S等人［6］利用社会认证建立备用的认证系统；Zhan J等人［7］进一步细化社会网络，将社会关系按强弱划分级别，低级别要到达认证级别，需更多担保人。尽管上述结论依赖线下社会关系，然而研究表明社会关系的强弱，不依赖于线上和线下。如Ellison N B等人［8］认为，绝大多数线上关系的建立基于已存在的线下关系；Ellison N 等人［9］甚至认为Facebook更倾向被用于维护和巩固线下关系而非认识新人。在具体如何利用社会关系构建网络身份的研究上，Maheswaran M 等人［10］进行初步探索。他们给OSN 增加一个虚根节点，利用其它节点到根节点的路径作为身份认证的因素。但是，这一身份模型没有考虑到社会关系的强弱之分，sybil节点的存在和网络的动态变化等问题。

本文提出的基于社会认证的网络身份SANI（Social Authenticated Network Identity）模型，采用担保形式的社会认证，能保证节点的真实性、边的牢固性和路径的有效性，并在不依赖实名信息的情况下得到安全可靠的SANI。SANI如同节点的身份证，能实现身份认证和行为溯源。

2 基于社会认证的网络身份模型

对OSN 进行分析时，我们一般将OSN 看成一张图，其中V为顶点集合，对应于用户集合，E为边集合，对应于关系的集合。另外，图G中的路径则对应于关系的传递。我们分别从点、边和路径出发，论述在线社会网络身份模型，并给出构建SANI的系统框架。

2.1 在线社会网络身份模型

我们讨论的身份问题是指“个人实体与数据关联的问题”，与Clarke R［11］所讨论的身份意义相同。下面我们讨论在OSN 中如何利用社会关系构建身份。

（1）Ego－Identity身份模型。

在网络中，以自己为中心，可绘制出一张以自我为中心的社会网络图，如图1所示。

Figure 1 Example of Ego－Identity graph图1 Ego－Identity图示例

图1中，d（x，Me）表示x和Me之间所有路径长度的最小值。该网络中，离自己越近的节点关系越亲密，即d越小意味着节点x与节点Me的联系越紧密。定义：

则在描述自中心的社会网络身份时，可定义x的身份为：

现实世界中，每个人自中心的社会网络是不同的，因此其可作为身份认证的依据。如EgoIdentity（Me）＝｛A，B，C｝｛D，E，F，G，H｝｛I，J，K，L｝可作为Me的身份标识。但是，在OSN 中，恶意用户可创建大量假节点来保护自己。

（2）Path－Identity身份模型

在网络中，增加虚拟根节点，其它节点到根节点的路径可作为该节点的身份，Maheswaran M 所提出的方案就是这一模型。该模型下，节点x的身份PathIdentity（x）＝［12，451］，为LandMark节点经节点b到x的边序列，如图2所示。

路径模型在一定程度上解决sybil节点问题，但仍存在其它问题。如路径存在问题，对边缘节点可能不存在到达Landmark 的路径；路径脆弱问题，OSN 中的节点间并非总是强关系，那么路径上任意一条边的脆弱都会导致整条路径的脆弱；网络动态变化问题，路径上任意节点或者边的失去，都会使路径失效。

Figure 2 Example of Path－Identity图2 Path－Identity示例

（3）基于社会认证的网络身份模型。

虽然Ego－Identity和Path－Identity都利用社会关系进行身份认证，但是它们都存在明显的不足。SANI模型结合了两者的优点，对社会关系有更深入的发掘。其既利用Ego－Identity中直接相邻节点间的社会关系最紧密的特性，又采用Path－Identity中路径认证抑制虚假节点的优势。另外，为解决OSN 中可能存在的虚假节点和弱关系问题，SANI采用担保形式的社会认证，使得参与身份构建的节点、边和路径的可靠性得到保证。我们会在3.1节中详细讨论社会认证和SANI的构建。

2.2 系统框架设计

系统的主要思想是采用担保方式完成对OSN中节点的社会认证并构建节点的身份。

图3描述了系统的框架。SNS服务器是OSN的提供者，维护社会网络的运行。在社会认证过程中，需要选择部分节点作为根节点，并由担保服务器进行服务器端认证，其它节点采用担保方式，由担保服务器完成担保认证。SANI服务器，依据SNS服务器和担保服务器，构建每个节点的SANI身份，并完成SANI的认证和网络监管中的溯源。

3 关键机制

本节描述系统社会认证、信任权值管理和行为溯源三大机制。社会认证机制是SANI的构建基础，我们将从根节点集的选择、层次化、担保认证和SANI构建四个方面详细论述。社会认证中节点的可信度是变化的，信任权值管理介绍如何描述节点的信任权值。行为溯源是SANI的应用，描述如何利用SANI中包含的社会认证信息对恶意行为进行溯源。

Figure 3 System framework图3 系统框架

3.1 社会认证

通常，个人实名信息PRNI（Personal Real Name Information），包含必须部分如用户名和身份证和可选部分如个人其它信息描述。

实名认证中前者为主要认证，后者作为辅助验证。相反，社会认证中，更重要的是社会关系的描述。在担保方式的社会认证中，用户的验证信息将会发送给朋友，我们定义为：

当然，这只是文本信息的验证。更严格的验证可采取语音、视频、图像等方式。用户不需发送实名信息给服务器，但为实现对全局身份的管理，定义发送至服务器的信息为，

即，将用户所加密的实名信息的必须部分的哈希值作为用户的全局身份IDglobal。

在OSN 中进行社会认证的具体过程包括根节点集的选择、层次化、担保认证和SANI的构建四个部分。

（1）根节点集的选择。

选择OSN 中的很少部分用户作为根节点集进行服务器端认证，记为SETroot。用户作为社会认证的起点和行为溯源的终点，其选择原则是中间度大和全局分散。中间度大的节点可靠性高，社会认证扩散快；全局分散的原则也是使社会认证扩散快。具体实施时，可对OSN 上的节点进行社区分析，选择那些中间度高的节点。中间度，即Betweenness Centrality，常用于分析社会网络中个体重要性，它表示所有的节点对之间通过该节点的最短路径条数。它很好地描述了一个网络中节点可能需要承载的流量。一个节点的中间度越大，流经它的数据分组越多，在OSN 中意味着媒介作用越大。定义为：

其中，σst表示所有由节点s到节点t的最短路径数量；σst（v）表示所有由节点s到节点t，经过节点v的最短路径数量。

（2）图G层次化。

担保认证一般是按照由高层往低层次进行的。层次化具体步骤为：

①定义SETroot中的节点在G中的层次为第1层I1；

②按照宽度优先算法进行扫描，忽略扫描过程中再次出现的节点；

③直至第In层结束，那么由I1，I2，…，In得到完全层次化的图G1。

（3）担保认证。

对于（1）中的SETroot节点，采用服务器认证（如实名认证），记为SAserver，个人认证信息需保存在服务器。其它的节点采用担保认证的方式，记为SAfriend，即用户需定义朋友关系组SETfriends；然后向SETfriends提交验证请求；最后由SETfriends验证并告知服务器。为防止恶意节点随意指定SETfriends，我们要求作为担保者的节点须是已被认证过的节点，记为SETsf，

如图4所示，为担保认证过程，参与者有：

Unverified User：待验证者，记为Userunverfied，是验证请求的发起者；

Verifiers：表示验证组，记为SETverifiers，对验证请求进行验证；

Vouching Server：担保服务器，记为Servervouching，维护全部节点的认证状态。

担保认证的具体过程：

①Userunverified，发送PRNItoFriends至SETverifiers，PRNItoServer至服务器；

②SETverifiers验证PRNItoFriends；

③SETverifiers告知Servervouching验证结果；

④Servervouching收集验证结果，确定Userunverified是否通过验证；若通过，则将Userunverified标记为SAfriends。

（4）SANI的构建。

Figure 4 Social authentication process by vouching图4 担保方式的社会认证过程

在SANI构造中，我们同时考虑节点的直接后继和节点与根节点间的路径。定义SANI为：

其中，

TypeSA为社会认证的类型，服务器认证或者担保认证；

Rootspath为所有认证路径的根节点集合；

Friendsfirstpass为首次达到社会认证条件时，所有担保节点的集合；

Friendsvoucher为朋友集合中，该节点担保者的集合；

Friendsasker为朋友集合中，该节点作为担保者的集合。

SANI中不直接保存所有的根路径，因为可能存在很多路径，而是提供足够的信息以还原根路径，我们设路径方向指向Root，则：Rootpath指明所有路径的根节点集合；Friendsvoucher指明所有路径上本节点的后继节点集合；Friendsasker指明所有路径上本节点的前驱节点的集合。

3.2 信任权值管理

SAserver认证的节点，其可信度最高；作为认证的启动过程，I2层上的节点，仅需SAserver认证的节点担保即可通过SAfriends认证；但其信任权值降低，意味着I2层上的节点提供担保时，需要更多的节点才能通过认证。随着信任层次传递，信任程度不断降低，我们定义位于第k层的节点，其层信任权值wlk（Trust Weight of Node Level）如表1所示。但是，SETroot是初次选择时已确定的，且数量很少。由于信任权值随着层次不断减小，下层节点的认证可能需要很多节点的担保，这可能导致某些节点无法满足社会认证条件。考虑到节点的可信程度除了与层次有关系外，还与节点的度有关系，特别是与节点的SETfriend的大小有关系。如果节点的度或节点的担保人较多，我们可适当增加其信任权值，定义节点k的度信任权值wdk（Trust Weight of Node Degree）。我们定义，Dk＝degree（k），表示节点k的度，这里的度必须是有双向连结；AVGDlk＝average（degree（lk）），表示第k层节点集的平均节点度；NUMsa（k）＝number（｛y｜y∈SETFriends（k）∧y∈SAsf｝），表示节点k的亲密关系组SETfriends（k）通过社会认证的数量。这些变量与wdk的关系如表2和表3所示。

Table 1 Trust weight of node level表1 按层次为节点所赋予的层次信任权值

Table 2 Trust weigth incrementΔ1affected by Dk表2 Dk 对权值增量Δ1 的影响

Table 3 Trust weight incrementΔ2affected by NUMsa（k）表3 NUMsa（k）对权值增量Δ2 的影响

最终，节点k的信任权值wk为：

在担保认证过程中，节点x通过担保认证的条件是：

其中，wi是节点x的担保节点信任权值。

3.3 行为溯源

行为溯源是指，当恶性行为发生时，我们可通过节点的SANI来追溯其现实身份。SANI中包含认证节点的路径信息，我们可根据SANI中的路径信息追溯到恶意节点对应的现实人。如，通过节点A的SANI，可找到对应的根节点和直接后继节点。如图5所示，节点A有三个担保节点V1、V2、V3，它们是A的朋友且通过社会认证（灰色节点），在图中表现为A的直接后继节点；虚线箭头表示中间的节点SANI，可通过迭代获得。

假设，节点A产生了恶意的行为，并且我们需要追溯A节点的现实身份，我们可以直接向V1、V2、V3询问A的现实身份。当然，根据V1、V2、V3的回复，又有不同的处理方式。

（1）回复一致。验证节点A的现实身份，如果符合，则达到溯源的目标；如果不符合，则V1、V2、V3的回复相当于恶意行为，分别对其进行溯源。

（2）回复不一致。对每个回复进行验证，如果符合，则该回复达到溯源目标，并且对其他回复的节点进行溯源；如果不符合，则对该节点进行溯源。

（3）部分回复。对已回复的节点按照（1）、（2）流程处理；对于未回复的节点，暂停其社会认证的标识，其相应的社交功能受到限制（比如无法发言），直至回复该询问。

（4）全没回复。同（3）。

Figure 5 Process of tracing real world identity图5 行为溯源过程

溯源过程是一个递归过程，终止于顶层节点SAserver，因为此类节点，用户的真实身份信息保存在服务器。针对节点的恶意行为及其担保者的担保活动，可以采取措施消减其信任权值。

4 社会认证模拟与安全性讨论

本节我们首先模拟社会认证过程中SETroot节点集的选择，然后对社会认证和SANI的安全性进行讨论。

4.1 社会认证模拟

限于实验环境限制，我们暂时难以开展OSN上实际的社会认证实验，而采用分析模拟的方式取代。因为担保过程需要节点间的相互交互，难以进行分析模拟，所以我们主要对选择过程和策略进行分析模拟。SETroot是社会认证过程的起点和行为溯源的终点，需要选择可靠性高且社会认证扩散速度快的节点。

如图6所示，是模拟的过程和结果。为便于可视化，我们选择大规模的OSN 中的部分样例。如图6a所示，它是本次模拟的社交网络拓扑图，为实际社交网络中极小的一部分，约330个节点，1 000条左右的边。对图6a进行社区发现算法，找到其中的社区，如图6b 所示。图6b 是通过walktrap算法得到的社区结构。每个社区中的节点关系相对紧密，便于社会认证的条件易满足。如果SETroot中的节点分散在每个社区，则会大大加速整个OSN 中社会认证的扩散。为了在每个社区选择中间媒介度高的节点，我们需要分析每个节点的中间度，如图6c所示，为所有节点的中间度分布。如果按照每个社区至少选择一个SETroot节点的思想，应该依据图6c的中间度分别在图6b每个社区中选择中间度最大的节点。但是，实际上，walktrap算法发现的社区并不一定准确，在本次模拟中，由于整个图较小，算法计算出来的社区大部分很小，于是我们剔除这些较小的社区。最后，我们选择中间度不小于3 000 的节点作为SETroot，如图6d所示，图中的大点即为我们选择的节点。

在实际的OSN 上，除了采用数据分析的方法外，我们还可以直接选择OSN 中的名人用户。这些名人用户，或为明星，或是领域专家，或是政府组织要员，其OSN 帐号的真实性能够得到保证；同时名人的社交范围广，一般能起到中间媒介作用，能够满足社会认证快速扩散的作用。

Figure 6 Simulation results图6 模拟过程和结果

4.2 安全性讨论

系统核心安全有两大部分：社会认证的安全和SANI本身的安全。社会认证的安全在文献［5］中已经有所讨论，这里我们进一步讨论全局标识IDglobal的安全性和SAserver节点的安全性。SANI的构造依赖OSN 拓扑结构，我们将分析构造过程的安全性。

（1）社会认证安全性。

①全局标识IDglobal的安全性。在同一SNS上用户可能注册了不同的账号，假设用户A在同一SNS下拥有账户A1、A2、A3，按照社会认证的流程，账号A1通过社会认证，如果无IDglobal则会出现自我担保和多账号他人担保的异常情况。在我们的设计中，恶意用户确实可能拥有两个以上的IDglobal，如果他们具有不同个人信息副本并与SETfriend共谋。但是，这种恶意行为产生的可能性极小且对系统核心安全无影响。首先，我们不收集用户的实名信息，从根本上消除用户因担心信息泄露而欺骗的动机；其次，攻击者并不能获取好处，却需付出相当大代价，如伪造身份信息和共谋；最后，即使成功伪造IDglobal，行为溯源依然可有效进行。因为行为溯源机制不关心担保节点与被担保者间依赖何种信息进行身份认证，而只关心他们之间是否存在强关系，而伪造IDglobal需要朋友共谋，这本身就说明两者间具有强关系，所以依然可通过SANI进行行为溯源。

②SAserver节点的安全性。SAserver节点作为社会认证的顶层节点，既是社会认证的起点，又是行为溯源的终点，为保证SAserver节点的真实性，我们需对其进行服务器端的身份认证。在采用实名认证的时候，考虑到SAserver节点的数量有限，变动小，社会认证时，实名信息不被使用等原因，可对实名信息物理隔离保护。另外，我们认为即使SAserver节点的实名信息泄露也不会对系统产生威胁，因为担保认证中不依赖实名信息。但是，实名信息的泄露确实会影响到SAserver节点所对应的现实人，但考虑泄露概率和数量，其造成的影响可忽略。

（2）SANI的安全性。

通常，攻击者比较容易获取OSN 上用户的朋友列表，但是要以此分析出某个节点的SANI在计算上是不可行的。参考SANI的构造，虽然攻击者通过分析能缩小被攻击节点的范围，但是却无法区分其前驱与后继节点；更进一步，攻击者也难以知道全局的服务器认证节点。下面，我们从被攻击节点的类型作进一步讨论。

随机节点的攻击。首先，如果不能确定哪些节点是SAserver节点，是无法进行有效攻击的；其次，进行随机节点攻击，要求知道所有的SAserver节点，这几乎是不可能的；最后，即使知道SAserver节点列表，其组合可能性也是计算不可行的。如，设SAserver有1 000个，其组合情况为：

2×21000×K

其中，K为其它参数可能的组合，因此随机节点攻击是最无效的。

针对服务器认证节点及其直接后继节点的攻击。如果攻击者已知某个节点是SAserver节点，则该节点的TypeSA和Rootspath泄漏；同时，其直接后继节点的TypeSA和Rootspath也泄漏。在这种最具威胁的情况下，我们认为双向连结BiTie的数量会很好地保证节点安全性。对于SAserver，在选择时已经保证其BiTie数量足够大，例如，对于拥有Bi－Tie数量为300名的SA 节点来说，其组合可能性为，

1×1×4300＝2600

最后，为保证其安全性，我们将使用IDglobal来保存SANI的信息，IDglobal是无法通过简单的社交网络分析得到的，因此攻击者无法通过数据分析和暴力破解得到SANI。

5 结束语

网络实名制解决了OSN 匿名性带来的实名信息泄漏的本质缺陷。本文发掘OSN 中的社会关系，提出基于社会认证的网络身份模型来解决这一问题。社会认证依赖的认证因素是社会关系而非实名信息，这样就从根本上消除了实名信息泄漏的隐患。在身份模型构建的讨论中，我们从点、边和路径角度分析如何利用社会关系去构建节点的身份，并最终采用基于社会认证的身份模型。在社会认证过程中，通过选择部分节点作为根节点，采用担保认证方式，使得OSN 中的节点都能通过其朋友节点的担保而进行社会认证。进一步，利用OSN 社会认证过程中的拓扑结构，在不依赖实名信息的基础上，构建每个节点的SANI身份。SANI能够唯一标识OSN 中该节点的身份，同时其蕴含社会认证的路径信息，使其具有行为溯源的功能。最后，我们对系统模型中的社会认证部分进行简易的模型模拟并对系统的安全性进行深入的讨论。总之，利用社会关系进行身份认证，可有效防止个人实名信息的泄漏并可对恶意行为进行溯源，在OSN 中具有重要现实应用和理论研究意义。当然，我们的研究还存在很多不足，比如社会认证过程中，如何保证认证的扩散速度；如何应对OSN中节点的新增和删除所带来的动态变化等，这将是以后工作的研究方向。

［1］ Song D H.Power struggles in Korean cyberspace and Korean cyber asylum seekers［J］.Cultural Policy，Criticism ＆ Management Research，2011，1（1）：47.

［2］ Cho D.Real name verification law on the Internet：A poison or cure for privacy？［M］∥Economics of Information Security and Privacy III，New York：Springer，2011：239－261.

［3］ Cho D，Kim S，Acquisti A.Empirical analysis of online anonymity and user behaviors：The impact of real name policy［C］∥Proc of the 45th Hawaii International Conference on System Science（HICSS），2012：3041－3050.

［4］ Oh Y，Obi T，Lee J S，et al.Empirical analysis of Internet identity misuse：Case study of South Korean real name system［C］∥Proc of the 6th ACM Workshop on Digital Identity Management，2010：27－34.

［5］ Brainard J，Juels A，Rivest R L，et al.Fourth－factor authentication：Somebody you know［C］∥Proc of the 13th ACM Conference on Computer and Communications Security，2006：168－178.

［6］ Schechter S，Egelman S，Reeder R W.It’s not what you know，but who you know［C］∥Proc of CHI’09，2009：1.

［7］ Zhan J，Fang X.Authentication using multi－level social networks［M］∥Knowledge Discovery，Knowlege Engineering and Knowledge Management，Berlin：Springer，2011：35－49.

［8］ Ellison N B.Social network sites：Definition，history，and scholarship［J］.Journal of Computer－Mediated Communication，2007，13（1）：210－230.

［9］ Ellison N，Steinfield C，Lampe C.The benefits of facebook“friends”：Exploring the relationship between college students’use of online social networks and social capital［J］.Journal of Computer－Mediated Communication，2007，12（4）：1143－1168.

［10］ Maheswaran M，Ali B，Ozguven H，et al.Online identities and social networking［M］∥Handbook of Social Network Technologies and Applications，New York：Springer，2010：241－267.

［11］ Clarke R.Human identification in information systems：Management challenges and public policy issues［J］.Information Technology ＆People，1994，7（4）：6－37.