CPU自动化测试
有幸和zlr同学一起开发462oj，这让我收获了一次非常宝贵的自动化测试经验。作为数据构造者，我想介绍一下评测机数据生成部分背后的一些细节，希望能从自动化数据生成的角度给同学们一些启示。
本文主要分享样例自动生成程序的思路（P4部分），分为四部分，分别是消除死循环、保证数据的正确性、扩大数据的覆盖范围和程序总体架构设计。
一.消除死循环
1.问题
死循环可谓是自动化数据生产的一大难题。这个问题不解决，那么在很有可能程序难以终止。讨论区的大佬们分别给出了不同的答案，比如固定跳跃次数等。
2.思路
经过不断的尝试后，我逐渐放弃了原先往后跳的思维定式，转为规定跳跃型指令必须向前跳。什么意思呢？比如说jr指令，我就必须要保证寄存器的值大于当前的PC，否则，干脆不跳。这种处理方法与我后面要谈到的在线模拟的思路相契合，简化了在线模拟的难度。
3.论证
我们不难证明，向前跳显然是不会导致死循环的，正确性上有了保证。那数据覆盖的全面性呢？其实，跳跃型指令检测的本身就是能不能保证PC能正确的指向下一条指令。那么，对于跳跃型指令本身，向前还是向后跳是没有区别的。至于其他指令的覆盖，只要我增强数据的规模，比如说1000条指令，那么向前条之后指令的检测率也能得到有效的保证。
二.保证数据的正确性
1.背景
通过浏览讨论区很多大佬的自动化生成数据思路，我受益良多。但是，通过对他们构造数据的进一步测试，我发现了一个问题：很多lw、sw指令指向非法的位置。
2.分析
为了探究产生这个问题的原因，我用Mars模拟了指令的行为，最终发现，原因由两部分组成，一是有些同学自身生成的lw、sw的偏移量并没有注意是4的倍数，二是虽然保证了直接的lw、sw偏移量是4的倍数，但是没有考虑到ori、lui等你指令对寄存器的改变。
3.解决方案
综合了上述的原因和分析，我想到了一个能完美解决这个问题的方案：将所有指令所涉及到的立即数都确保为4的倍数（通过同余定理可以证明最终所有的数都是4的倍数）。这个解决方案虽然从一定程度上削减了数据的多样性，但是大大简化了数据生成方面的复杂度，怎么算都是值得的。
1.问题
通过对数据生成方面的实践，我逐渐意识到，地址边界的问题也着实需要考虑。在2023年CPU构造要求中，对指令存储器和数据存储器的大小均有要求，如果一味的随机化处理，那势必难以保证寄存器中的值满足存储器的范围。
2.解决方案
为了解决这个问题，我曾经尝试过很多不同的方案。刚开始的时候，我本来想通过随机化的后续跟踪测试来确认数据的合法性。但是通过实测，我发现这样生成的数据错误率过高，如果每次都是先数据生成再数据检测，那么数据的生产效率将会大大降低。在多次试错后，我产生了一种在线跟踪测试的想法。即在指令执行的同时，通过数组来仿真指令的行为（其实就是用高级语言来实现低级语言。先将高级语言编译成低级语言，再用低级语言来实现低级语言，啊啊啊~）。总之，通过同步的模拟，我可以很明确的保证每一步生成的指令从开始到现在都是合法的。这样的跟踪能够及时的进行纠错，大大提高了数据生成的效率。
三.扩大数据的覆盖范围
1.背景
自动化测试的本质就是帮助同学们在课下尽可能全面的测试CPU的各个模块，从边界和特殊情况来确保指令执行的正确性。所以数据的覆盖范围至关重要。
2.数据生成思路
在构造数据之前，我也对这个问题进行了很多的思考。在最终实现的时候，我将我能想到的思路都实现在了我的自动化生成代码中。首先，我明确了跳转结点的个数，决定了它们在指令中的位置。然后，在这些跳转结点之间，插入其他指令（满足正确性），尽量用rand使指令的分布接近于真实CPU的指令分布。最后，我通过随机和corner case检验来覆盖尽可能多的情况。
3.不足和改进
通过在自动化测试中一些同学的反馈，本次P4生成的数据随机不够彻底，边界测试还做得不充足。针对这些问题，我仔细思考并初步构思了下一步的改进策略。首先就是随机化生成部分，由于是第一次尝试构造数据，我只是简单的使用rand来生成数据，并不能保证数据分布的完全随机（伪随机数）。在下一步的改进中，我打算使用mt19937和伪蒙特卡洛算法对随机进行进一步的优化。其次，我可以再针对DM和IFC中的边界情况进行更多的倾斜，让更多的指令能覆盖到这些边界的情况，尽量提高指令之间的差异度。
四.程序总体架构设计
在前面的叙述中，相信同学们也能对我的自动化生成思路有了一个大致的了解，现在，我想通过部分代码的展示，来进一步解释我的自动化数据生产的思路。
1 | start: |
这个板块是lw的设计，主要结合了上述关于数据正确性保证的相关思路。可以发现，如果我检测到了lw的地址超出了题目要求的地址，我的程序就会跳转重来，直到它生成符合要求的数据为止。如果数据符合要求，我就用r和nei数组来模拟这次lw操作。
1 | for(int a=0;a<32;++a){ |
这个板块是jr的设计，主要结合了上述关于正确性保证和消除死循环的相关思路。可以看到，我对寄存器中各种非法的jr指令进行了判断和消除，直到找到一个正确的寄存器满足jr转跳的条件，最终执行转跳操作。
在总体架构设计上，我主要采用了循环+随机+分指令处理的模式，对每一条指令进行分类处理。增加了代码的模块化，也便于日后增加新指令，提高了程序的可扩展性。
总结与展望
这次CPU自动化数据生成工作让我收获了思考上的乐趣和很多宝贵的经验。同学们也在我们帖子下方积极留言，这让我感觉到很欣慰。在今后的P5、P6、P7中，我会继续思考，优化当前的数据生成工作，希望最终臻至佳境。最后十分感谢同学们和助教团队对462oj的大力支持，我们将努力精进，不负大家的期待！！！
同学好，你对自己的数据生成策略的测试覆盖率与正确性等指标进行了具体的分析，介绍涉及面广泛，这种分享精神值得鼓励。
但是帖子中仍然存在一些问题需要指出，比如：只向前跳转并不能保证覆盖率，即便是增强数据规模也难以做到。举例说明，向后跳转利用了补码运算的特性，其依赖扩展器/扩展逻辑的正确性，如果某同学将分支跳转所用到的立即数扩展误实现为 0 扩展，那么在向后跳转的过程中就会出现错误。又比如，不应为了简化数据生成的复杂度而向测试的覆盖率妥协。
更具体的细节问题我不再赘述，这部分将交由数据组的助教来解答。总而言之，我们鼓励一切有关测试的分享，但我们更希望大家能在构造数据的过程中尽自己最大的努力去保证数据的强度（即测试覆盖率），若能在此基础上进一步实现自动化的数据生成，那……计组助教团队欢迎你的加入！