之前跟大家分享了我前些日子遇到的一个失败的例子,有大佬后台私信指点了我一把,感谢大佬!
这段时间在逐渐的拆分各个模块,比如构图,修复调用关系,都用了不同的Phase来区分顺序,我自己也对这部分的逻辑清晰了许多,之前其实有不少的逻辑错误,这下都修复的七七八八了
顺带着把Java的语法也再次仔细的看了看,比如容易漏掉的抽象类,抽象类继承抽象类,抽象类的抽象方法,多重继承未实现的Override方法,比如一个类有父类也有子类,它的Override方法可以不实现,这些逻辑调用边是极其容易漏掉的,以前多次提过这个,我也顺着这个思路捡了一些无关痛痒的漏洞
但是始终有一个问题我没有解决,有些路径搜索会陷入奇怪的情况无法跳出搜索
以美团外卖来举例,我在进行搜索解压缩路径穿越漏洞的时候,发现有一个节点始终不能完成搜索
我先描述下我这里的搜索思路:我构图的时候,实现的是有向图,比如一个节点Lcom/sankuai/waimai/platform/capacity/immersed/a;->a(Landroid/app/Activity;)Z
,它存储了所有调用它的节点,也存储了它调用的所有节点,也就是说任意两个邻接节点中间必存在两条指向相反的边,但我们搜索的时候,只会使用一种类型的边,要么都是Caller,要么都是Callee
因为我对边的设定,在搜索的时候就会出现两种方式,一种是从指定入口开始搜索,比如导出组件的入口方法开始搜索我们的关键节点,另一种是从关键节点反向搜索到最顶层的调用
这两种方法有利有弊
第一种方法能够更加直接的指出入口可控的路径,但它会漏掉一部分结果,因为有可能存在没有完全补全的边,那搜不到关键节点就会退回,导致这条路径被错过
第二种方法会搜索出很多乱七八糟的路径,很多路径是不可达的,或者说是不可控的,但我们可以通过分析它搜索出的顶层节点来补全很多漏掉的边,就像上次我说的Runnable
接口的方法run()
,还有大佬跟说的Thread
和AsyncTask
我目前还使用的是第二种,逐渐补全,第一种可以在后续用的比较稳定之后再使用
回到我一开始遇到的那个问题,我在搜索Lcom/meituan/android/cipstorage/MMKV;->a(Landroid/content/Context;)Z
的时候,发现一直出不来,这就很奇怪了
一开始我想的是成环了,导致一直在一个环里跑,后来仔细一想,不可能的,因为我搜索的时候会判断如果当前节点已加入路径就跳过,也就是说,一个正在搜索的路径是不会重复进入自己这个节点的,那也就不会成环
如果有同学也遇到了这个问题,可以考虑先判断环的问题
在有向图里判断环有很多方法,常见的比如DFS深搜,可以在一轮搜索里面维护一个节点标志位,判断这个节点是否被搜索过,一共有三种状态:未被搜索过,之前搜索过,本轮搜索过,那当遇到一个本轮搜索过的节点,就可以判断环的存在
或者可以用拓扑排序,它的代码处理过程就是不断的把入度为0的节点从图上剥离,然后把被剥离掉的这个节点指向它邻接节点的边也给去掉,重复这个过程,最后如果还有节点,说明存在环
我简单画了个图来理解,节点1,2,3,4成环,节点5,6属于入度为0的节点,可以剥离,同时去除节点5指向节点1的边,去除节点6指向节点2和节点7的边
第一次剥离后,节点7成为入度为0的节点,进行剥离,去除节点7指向节点3和节点8的边
第二次剥离后,节点8成为入度为0的节点,进行剥离,同时去除节点8指向节点4的边
最后就剩下节点1,2,3,4成为一个环,每个节点入度都不为0,此时我们就可以判断当前有向图存在环
回到我遇到的问题
想着想着确实是没有思路了,我决定把图可视化,我一开始简单的画了一下模拟图,找找感觉
通过操作Neo4j图数据库来完成可视化,下面这幅图是全节点图,也可以从关键节点开始搜索,记录调用它的节点,然后添加这两个节点的关系,重复这个过程,把所有关联到的节点全都添加进去,由于配置问题,这里并没有展示出所有节点
在写这篇文章的时候,我为了截图说明,跑了一下代码进行测试,结果写完文章之后,发现结果出来了,竟然只花了十分钟,不科学,那天晚上的时间没有这么短啊
那现在可以可视化的思考为什么搜索出不来的问题了
正常情况下我们还可以对比思考,比如多生成几个关键节点的图,这里的关键节点是调用了Ljava/util/zip/ZipEntry;->getName()Ljava/lang/String;
的节点,可能有十个,几十个,几百个
之前其实挺害怕卡在一个搜索里出不来的,因为排查起来特别费劲,搜索这种东西,又不知道到底搜索到哪里了,是性能的问题,还是代码的问题,只能靠猜,可视化之后就感觉好很多了,以后再遇到这种问题,可以先分析,再做优化