深度分析的基本思想是,从某个类型的子图中寻找 Connected Component ( 连通分量,后简称 CC ), 对 CC 进行画像,定位出存在异常的 CC,再从这个 CC 出发寻找与之相关联的订单或其他节点。
在挑选子图时,尽可能选择一些强关联关系,比如邀请关系 ,邀请者与被邀请者是具体的,事实的存在。而像 Account -(use_ip)-> IP
这样的关联,并非稳定关系,尤其是在中国 IPv4 地址资源有限的环境下,绝大多数人上网使用的是动态 IP,一个 IP 在一段时间内可能为黑产所用,在另一段时间可能是一个正常用户在用。
关系的强弱稳定,在不同场景下是不一样的,需要具体问题具体分析。读者也可以思考一下,在动态 IP 环境下,账户与IP之间的关联关系是否完全失去意义,是否可能有其他利用价值。这部分内容我们留到下一个案例来讨论,学完之后将更能体会到,基于对业务的认识采用适合的 Schema 设计,可以很大程度提升分析效率。
在这个案例中,我们所说到的 CC,特指由邀请关系 构成的子图中的连通分量。
前面说到,因为成本效益的考虑,黑产团伙会尽可能资源使用成本,这样一来必然会在某些资源上出现共用,或者体现出一些独特的使用策略。
具体来说,在本案例中,我认为黑产团伙构成的 CC 可能具备如下特征:
如何寻找 CC
在这个案例中,邀请关系构成的子图是一个有向无环图 ( Directed Acyclic Graph ) ,在有向无环图中寻找 Connected Components,最简单的方法就是先寻找 CC 的祖先 ( ancestor ),即某个 CC 中,唯一一个入度( in-degree )为 0 的节点。可以用祖先节点的 id,作为 CC 的 id。
寻找 CC 的方法如下,忽略不必要的代码部分:
复制 ...
MaxAccum < VERTEX > @ancestor;
all_accounts = {Account. * };
ancestors =
SELECT t
FROM all_accounts:t
WHERE t.outdegree( "invite" ) > 0 AND
t.outdegree( "reverse_invite" ) == 0
ACCUM t.@ancestor = t
;
children = ancestors;
WHILE (children.size() > 0 ) DO
children =
SELECT t
FROM children:s - (invite:e) -> Account:t
ACCUM t.@ancestor = s.@ancestor;
END ;
...
使用一个节点累加器 @ancestor
来存储每个节点的祖先 id,这里用 MaxAccum 和 MinAccum 是一样的。第一次遍历,先寻找图中所有出度大于0,入度等于0的节点,令他们的 @ancestor
等于自己。然后从这些祖先出发,一步一步告诉自己的邻居,自己的祖先是谁。循环结束之后,全图所有的节点,都知道自己的祖先是谁。
深度过大的 CC
很多时候,由于活动规则的限定,加上黑产本身有避免被追踪的动机,黑产团伙会避免一个账号邀请过多的人。体现在图上,会发现黑产的邀请关系往往深度很大,在传统关系型数据库中,要计算一个邀请链条的深度,是一件开销很大的事情。当然,更深的邀请关系,还有成本效益上的考量,这点后面会再次提到。
代码 执行结果
复制 CREATE QUERY comps_depth_rank( INT k) FOR GRAPH MyGraph {
TYPEDEF TUPLE < VERTEX ancestor, INT depth > comp_depth;
MaxAccum < VERTEX > @ancestor;
ListAccum < VERTEX > @invite_chain;
GroupByAccum < VERTEX ancestor, MaxAccum <INT> depth > @@comp_depth_stats;
HeapAccum < comp_depth > (k, depth DESC ) @@comps_depth_rank;
all_accounts = {Account. * };
/*
寻找所有 cc 的祖先
*/
ancestors =
SELECT t
FROM all_accounts:t
WHERE t.outdegree( "invite" ) > 0 AND t.outdegree( "reverse_invite" ) == 0
ACCUM t.@ancestor = t
;
/*
将祖先信息传递到所有节点,并在每个节点上记录从祖先出发到达该节点,中途经过的节点
*/
children = ancestors;
WHILE (children.size() > 0 ) LIMIT 30 DO
children =
SELECT t
FROM children:s - (invite:e) -> Account:t
ACCUM t.@ancestor = s.@ancestor,
t.@invite_chain = (s.@invite_chain + [s])
;
END ;
/*
统计每个 cc 最深的邀请链条有多少层
*/
_t0 =
SELECT t
FROM all_accounts:t
ACCUM @@comp_depth_stats += (t.@ancestor -> t.@invite_chain. size ())
;
/*
保留 top k 个最深的 cc,作为结果返回
*/
FOREACH (ancestor, depth) IN @@comp_depth_stats DO
@@comps_depth_rank += comp_depth(ancestor, depth);
END ;
FOREACH c IN @@comps_depth_rank DO
PRINT c.ancestor AS ancestor,
c.depth AS depth
;
END ;
}
以 k=10
作为参数执行脚本,找出最深的 10 个 cc
复制 [
{
"ancestor" : "1879" ,
"depth" : 30
} ,
{
"ancestor" : "2704" ,
"depth" : 30
} ,
{
"ancestor" : "5283" ,
"depth" : 30
} ,
{
"ancestor" : "2090" ,
"depth" : 30
} ,
{
"ancestor" : "361" ,
"depth" : 30
} ,
{
"ancestor" : "1275" ,
"depth" : 26
} ,
{
"ancestor" : "855" ,
"depth" : 24
} ,
{
"ancestor" : "5491" ,
"depth" : 22
} ,
{
"ancestor" : "1919" ,
"depth" : 19
} ,
{
"ancestor" : "5390" ,
"depth" : 16
}
]
在之前的案例中,我们已经接触到了 tuple 和 HeapAccum 的用法。TYPEDEF TUPLE
定义一个 tuple 型数据结构,相当于 python 中的 namedtuple 。他常常与 HeapAccum 配合使用,用来对结果进行排序,并保留最大或者最小的 K 个结果。
GroupByAccum 和 MapAccum 很类似,区别在于 GroupByAccum 的 key 是一些基础类型,value 是累加器,并且 key 和 value 都可以有多个。比如,你想分别统计全国所有城市,每个月份气温的最高值、最低值与平均值,你可以定义这样一个 GroupByAccum
复制 GroupByAccum <
STRING city,
STRING month ,
MaxAccum <FLOAT> max_temp,
MinAccum <FLOAT> min_temp,
AvgAccum <FLOAT> avg_temp
> @@city_temp_stats;
...
@@city_temp_stats += ( "北京" , "1月" -> 0 , 0 , 0 );
@@city_temp_stats += ( "北京" , "1月" -> - 1 , - 1 , - 1 );
...
@@city_temp_stats += ( "北京" , "2月" -> 5 , 5 , 5 );
...
@@city_temp_stats += ( "上海" , "1月" -> 2 , 2 , 2 );
...
// 访问 GroupByAccum 的几种方式
// 1 . 获取上海2月平均气温
@@city_temp_stats.get( "上海" , "2月" ).avg_temp
// 2 . foreach 遍历每个分组
FOREACH g IN @@city_temp_stats DO
PRINT g.city, g.month, g.max_temp, g.min_temp, g.avg_temp
END ;
// 3 . foreach 遍历每个分组,类似 python 做一个 unpack
FOREACH (city, month , max_temp, min_temp, avg_temp) in @@city_temp_stats DO
PRINT city, month , max_temp, min_temp, avg_temp
END ;
下图展示的是发现的最深的一个 cc
非对己订单比例很高的 CC
正常情况下,用户邀请别人注册,得到的话费奖励,会给自己的手机号充值。黑产更多的则是拿出去变现,即消耗自己的积分给别的手机号充值,这里我们称之为非对己订单 。一个 CC 中如果非对己订单比例很高,则该 CC 受控于黑产团伙的概率就很大。
下图中浅蓝色的点代表账号,紫色的点代表订单:
代码 执行结果
comps_nonself_order_ratio_rank.gsql
复制 CREATE QUERY comps_nonself_order_ratio_rank( INT min_num_orders, INT k) FOR GRAPH MyGraph {
TYPEDEF TUPLE < VERTEX ancestor,
INT num_orders,
INT num_nonself_orders,
DOUBLE nonself_order_ratio > tp_comp_stat;
MaxAccum < VERTEX > @ancestor, @order_recvr;
GroupByAccum < VERTEX ancestor,
SumAccum <INT> num_orders,
SumAccum <INT> num_nonself_orders > @@ancestor_order_counter;
HeapAccum < tp_comp_stat > (k, nonself_order_ratio DESC ) @@comps_stats;
all_accounts = {Account. * };
all_orders = {BonusOrder. * };
/*
寻找所有的祖先
*/
ancestors =
SELECT t
FROM all_accounts:t
WHERE t.outdegree( "invite" ) > 0 AND t.outdegree( "reverse_invite" ) == 0
ACCUM t.@ancestor = t
;
/*
将祖先信息传播到所有节点
*/
children = ancestors;
WHILE (children.size() > 0 ) DO
children =
SELECT t
FROM children:s - (invite:e) -> Account:t
ACCUM t.@ancestor = s.@ancestor
;
END ;
/*
将奖励接收人信息,记录到 order 节点上
*/
_t0 =
SELECT t
FROM all_orders:s - (recv_bonus:e) -> Account:t
ACCUM s.@order_recvr = t
;
/*
对比奖励的发送人和接收人,分别统计每个 CC 的对己订单数与非对己订单数
*/
_t1 =
SELECT t
FROM all_accounts:s - (send_bonus:e) -> BonusOrder:t
ACCUM
CASE
WHEN s == t.@order_recvr
THEN @@ancestor_order_counter += (s.@ancestor -> 1 , 0 )
ELSE @@ancestor_order_counter += (s.@ancestor -> 1 , 1 )
END
;
/*
按照非对己订单比例对 cc 进行排序
*/
FOREACH (ancestor, num_orders, num_nonself_orders) IN @@ancestor_order_counter DO
IF num_orders >= min_num_orders THEN
@@comps_stats += tp_comp_stat(
ancestor, num_orders, num_nonself_orders, 1 . 0 * num_nonself_orders / num_orders
);
END ;
END ;
FOREACH g IN @@comps_stats DO
PRINT g.ancestor AS ancestor,
g.num_orders AS num_orders,
g.num_nonself_orders AS num_nonself_orders,
g.nonself_order_ratio AS nonself_order_ratio
;
END ;
}
以 k=10
,min_num_orders=10
作为参数,执行该脚本
复制 [
{
"ancestor" : "6597" ,
"num_orders" : 21 ,
"num_nonself_orders" : 21 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "2090" ,
"num_orders" : 52 ,
"num_nonself_orders" : 52 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "1837" ,
"num_orders" : 16 ,
"num_nonself_orders" : 16 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "2386" ,
"num_orders" : 11 ,
"num_nonself_orders" : 11 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "7729" ,
"num_orders" : 11 ,
"num_nonself_orders" : 11 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "7277" ,
"num_orders" : 15 ,
"num_nonself_orders" : 15 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "6582" ,
"num_orders" : 13 ,
"num_nonself_orders" : 13 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "7419" ,
"num_orders" : 10 ,
"num_nonself_orders" : 10 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "5954" ,
"num_orders" : 11 ,
"num_nonself_orders" : 11 ,
"nonself_order_ratio" : 1
} ,
{
"ancestor" : "2390" ,
"num_orders" : 16 ,
"num_nonself_orders" : 16 ,
"nonself_order_ratio" : 1
}
]
这个部分没有什么新的知识点,新的语法是在 ACCUM
操作中使用 CASE WHEN
语句来做分支判断。我们为该查询定义了一个 min_num_orders
阈值参数,只有 CC 中的订单数超过阈值的,才会考虑。
下图展示的 CC,非对己订单比例为 1,可以看到,这个 CC 中各账号获得的奖励,都充值给了中间的那个账号。
CC中存在大量设备共用
下图中浅蓝色的点代表账号,粉红色的点代表设备:
代码 执行结果
comps_share_device_rate_rank.gsql
复制 CREATE QUERY comps_share_device_rate_rank( INT min_comp_size, INT k) FOR GRAPH MyGraph {
TYPEDEF TUPLE < VERTEX ancestor, FLOAT share_device_rate, INT num_accounts > tp_comp_sdr;
MaxAccum < VERTEX > @ancestor;
GroupByAccum < VERTEX ancestor, VERTEX imei, SetAccum < VERTEX > accounts > @@accounts_grby_anc_imei;
GroupByAccum < VERTEX ancestor, AvgAccum share_device_rate, SetAccum < VERTEX > accounts > @@comps_counter;
HeapAccum < tp_comp_sdr > (k, share_device_rate DESC ) @@comps_stats;
all_accounts = {Account. * };
/*
寻找所有的祖先
*/
ancestors =
SELECT t
FROM all_accounts:t
WHERE t.outdegree( "invite" ) > 0 AND t.outdegree( "reverse_invite" ) == 0
ACCUM t.@ancestor = t
;
/*
将祖先信息传播到所有节点
*/
children = ancestors;
WHILE (children.size() > 0 ) DO
_t0 =
SELECT t
FROM children:s - (use_imei:e) -> IMEI:t
ACCUM @@accounts_grby_anc_imei += (s.@ancestor, t -> s)
;
children =
SELECT t
FROM children:s - (invite:e) -> Account:t
ACCUM t.@ancestor = s.@ancestor
;
END ;
FOREACH (ancestor, imei, accounts) IN @@accounts_grby_anc_imei DO
@@comps_counter += (ancestor -> accounts.size(), accounts);
END ;
FOREACH (ancestor, share_device_rate, accounts) IN @@comps_counter DO
IF accounts.size() >= min_comp_size THEN
@@comps_stats += tp_comp_sdr(ancestor, share_device_rate, accounts.size());
END ;
END ;
FOREACH c IN @@comps_stats DO
PRINT c.ancestor AS ancestor,
c.share_device_rate AS share_device_rate,
c.num_accounts As num_accounts
;
END ;
}
以 min_comp_size=30
,k=10
作为参数,执行脚本。
复制 [
{
"ancestor" : "1879" ,
"share_device_rate" : 21 ,
"num_accounts" : 42
} ,
{
"ancestor" : "5283" ,
"share_device_rate" : 19.6 ,
"num_accounts" : 98
} ,
{
"ancestor" : "8017" ,
"share_device_rate" : 18 ,
"num_accounts" : 36
} ,
{
"ancestor" : "6606" ,
"share_device_rate" : 4.625 ,
"num_accounts" : 37
} ,
{
"ancestor" : "7753" ,
"share_device_rate" : 4.04762 ,
"num_accounts" : 85
} ,
{
"ancestor" : "361" ,
"share_device_rate" : 3.57143 ,
"num_accounts" : 75
} ,
{
"ancestor" : "3236" ,
"share_device_rate" : 3.33333 ,
"num_accounts" : 60
} ,
{
"ancestor" : "2090" ,
"share_device_rate" : 3.09091 ,
"num_accounts" : 34
} ,
{
"ancestor" : "6597" ,
"share_device_rate" : 2.90909 ,
"num_accounts" : 32
} ,
{
"ancestor" : "8660" ,
"share_device_rate" : 2.05556 ,
"num_accounts" : 37
}
]
这个语句不涉及到新的语法。大体思路是,用两个 GroupByAccum,@@accounts_grby_anc_imei
的 key 是 (ancestor, imei),统计每个 CC ,每个 imei 下对应的账号数。然后在用 @@comps_counter
来统计每个 CC 下平均一个 IMEI 对应对少个账号。
下图展示来一个高设备共用率 的 CC:
可以看出,这个 CC 中大部分账号都共用了一台手机
CC的行为疑似机器操作
这里说的行为疑似机器,想表达的是,CC的行为,看上去像是一个预谋好的,有策略性的,由脚本控制的活动。
我们之前不断说过,黑产与反黑产的对抗,本质就是成本与效益的博弈,黑产团伙使用的资源都是有成本的,只有成本低于收益的时候,才有利可图。如何更加有效的利用资源,是黑产团伙的核心技术。
假设某优惠活动的规则如下,每邀请 3 个人,则可以换取一份奖励,某个黑产团伙一共拥有 10 个手机号。那么对于这次营销活动,他们有以下这 3 种薅羊毛策略。
策略 1 有浪费,策略 2、3 效率相同。但是策略 2 容易暴露,因此多数黑产会使用策略 3。
因此黑产 CC 在邀请关系图上,会体现出如下特征:
一个 CC 中,有邀请过别人的账号,我们称之为邀请者 ,如果营销活动的规则是邀请10个人可以兑换一份奖品,那么黑产 CC 中,每个邀请者一定会不多不少刚刚好邀请 10 个人,这样才不会造成资源浪费。
那么如何来衡量一个 CC 中,邀请者邀请人数 的均匀程度呢?统计我们常常用基尼系数 ( Gini Coefficient ) 来衡量均匀程度。
基尼系数为洛伦兹曲线与45度直线构成的区域的面积占三角形面积的比例
过去,基尼系数常常被用来衡量一个国家的贫富分化程度。我们将一个国家所有人的收入从低到高排序,洛伦兹曲线上的点,代表收入最低的 k% 的人口拥有 n% 的社会总财富。这个曲线越陡峭,说明大多数人掌握社会的少部分财富 ,贫富分化严重,基尼系数很大。
在黑产 CC 识别中,我们运用类似的思想,对一个 CC 中所有邀请者邀请的人数构成的数列,求基尼系数。黑产团伙的基尼系数往往很低,接近于 0。
基尼系数的一种计算方法:
G = ∑ i = 1 n ∑ j = 1 n ∣ x i − x j ∣ 2 n ∑ i = 1 n x i G = \frac{\sum_{i=1}^{n}\sum_{j=1}^{n}{|x_{i}-x_{j}|}}{2n\sum_{i=1}^{n}{x_i}} G = 2 n ∑ i = 1 n x i ∑ i = 1 n ∑ j = 1 n ∣ x i − x j ∣ 代码 执行结果
复制 CREATE QUERY comps_gini_rank( INT k = 100 , INT min_comp_size = 30 ) FOR GRAPH MyGraph {
TYPEDEF TUPLE < VERTEX ancestor,
INT comp_depth,
INT comp_size,
DOUBLE gini > tp_comp_stat;
MaxAccum < VERTEX > @ancestor;
GroupByAccum < VERTEX ancestor, VERTEX sendr,
SumAccum <INT> num_recvrs > @@num_recvrs_grby_ancestor_sendr;
MapAccum < VERTEX, MaxAccum <INT>> @@comp_depth;
MapAccum < VERTEX, SumAccum <INT>> @@comp_size;
MapAccum < VERTEX, BagAccum <INT>> @@num_recvrs_arr;
HeapAccum < tp_comp_stat > (k, gini) @@comp_stats;
INT depth = 1 ;
INT comp_depth = 0 ;
INT sum_diffs;
INT sum_arr;
DOUBLE gini;
all_accounts = {Account. * };
all_orders = {BonusOrder. * };
ancestors =
SELECT t
FROM all_accounts:t
WHERE t.outdegree( "invite" ) > 0 AND t.outdegree( "reverse_invite" ) == 0
ACCUM t.@ancestor = t,
@@comp_size += (t -> 1 )
;
children = ancestors;
WHILE (children.size() > 0 ) DO
children =
SELECT t
FROM children:s - (invite:e) -> Account:t
ACCUM t.@ancestor += s.@ancestor,
@@comp_depth += (s.@ancestor -> depth),
@@comp_size += (s.@ancestor -> 1 ),
@@num_recvrs_grby_ancestor_sendr += (s.@ancestor, s -> 1 )
;
depth = depth + 1 ;
END ;
FOREACH (ancestor, sendr, num_recvrs) IN @@num_recvrs_grby_ancestor_sendr DO
@@num_recvrs_arr += (ancestor -> num_recvrs);
END ;
FOREACH (ancestor, comp_size) IN @@comp_size DO
sum_diffs = 0 ;
sum_arr = 0 ;
gini = 0 ;
FOREACH x1 IN @@num_recvrs_arr.get(ancestor) DO
sum_arr = sum_arr + x1;
FOREACH x2 IN @@num_recvrs_arr.get(ancestor) DO
sum_diffs = sum_diffs + abs (x1 - x2);
END ;
END ;
gini = 0 . 5 * sum_diffs / (@@num_recvrs_arr.get(ancestor). size () * sum_arr);
IF comp_size >= min_comp_size THEN
@@comp_stats += tp_comp_stat(
ancestor,
@@comp_depth.get(ancestor),
comp_size,
gini
);
END ;
END ;
FOREACH comp_stat IN @@comp_stats DO
PRINT comp_stat.ancestor AS ancestor,
comp_stat.comp_depth AS comp_depth,
comp_stat.comp_size AS comp_size,
comp_stat.gini AS gini
;
END ;
}
以 min_comp_size=30
,k=10
执行该脚本
复制 [
{
"ancestor" : "8262" ,
"comp_depth" : 5 ,
"comp_size" : 71 ,
"gini" : 0
} ,
{
"ancestor" : "8433" ,
"comp_depth" : 2 ,
"comp_size" : 31 ,
"gini" : 0
} ,
{
"ancestor" : "5628" ,
"comp_depth" : 3 ,
"comp_size" : 31 ,
"gini" : 0
} ,
{
"ancestor" : "8440" ,
"comp_depth" : 9 ,
"comp_size" : 91 ,
"gini" : 0
} ,
{
"ancestor" : "11584" ,
"comp_depth" : 2 ,
"comp_size" : 31 ,
"gini" : 0
} ,
{
"ancestor" : "4231" ,
"comp_depth" : 5 ,
"comp_size" : 51 ,
"gini" : 0
} ,
{
"ancestor" : "8478" ,
"comp_depth" : 2 ,
"comp_size" : 31 ,
"gini" : 0
} ,
{
"ancestor" : "6678" ,
"comp_depth" : 3 ,
"comp_size" : 51 ,
"gini" : 0
} ,
{
"ancestor" : "15928" ,
"comp_depth" : 4 ,
"comp_size" : 41 ,
"gini" : 0
} ,
{
"ancestor" : "11686" ,
"comp_depth" : 4 ,
"comp_size" : 41 ,
"gini" : 0
}
]
这个查询语句除了麻烦一点,和之前的相比,并不算太复杂。先统计每个 CC 下,每个邀请者,邀请的人数。然后对每个 CC 进行统计,计算基尼系数。除此之外,该语句还顺便统计了一下 CC 对深度和大小。
上图分别展示了不同基尼系数的 2 个 CC 的邀请关系图。基尼系数更小的 CC,更有可能是黑产行为。