-
-
[原创][庄周梦蝶]兔斯基保护协会提供的题目解法，相关数学，可能需要的自动机
-
2019-9-17 19:21
-
下面有python源代码：（附件是缩进良好的源代码）
python3直接可以跑，python2也许也可以，我没用啥高级函数。
源代码第一部分是，虚拟机和题目机制解说，源代码加注释
源代码第二部分是，有效解（正确答案）的得出，解空间数学证明
源代码第三部分是，解枚举自动机
铺垫：
我的程序极小，代码很短，没加壳，可以通过IDA静态分析得到题目的代码架构如下图：
推荐判断方法：（对于有协议分析或者数据结构分析经验的选手，更容易找到关键点）
1，可以分析出虚拟指令集，只有10种指令，而且非常简练（见下文python代码）。指令集只能访问其中两块内存，其中一块是128个范围为 0-127 的数字，无重复，记作数组A；另一块是范围 0-255 的数字，但只有128个，且无重复，记作数组B.
A 和 B 在IDA中的位置见下图：dword_4143F0就是数组A，dword_413FF0就是数组B
2，看结果判定的部分知，用于和计算结果比对的是一个由128个范围 0-127 的数字组成的数组，记作数组C. 指令集不能操作数组C.
数组C在IDA中的代码位置如下图：
数组C在IDA中的内存如下图。是不是特征很明显？（我特意用int类型存放，以突出其是0-127的数组的特点。有数据结构逆向经验者，会觉得这比Offset+Length或者Length+Pointer的结构还明显，这就是个索引。当然，不需要这步就看出来，可以第3步再发现）
3，结合指令集的限制，和结果判断方式，我们主要研究A，B，C的关系，而这道题也明显应从数据特征分析入手。从A，C的构成来看，很明显有是索引的可能。用数组C的索引访问数组B，是升序排列。可见是个排序题。（总共就3块数据，来回排列组合式的看看关系，也能看到升序数列，有python代码清晰展示这三块数据的内容）
A = [29, 76, 10, 59, 66, 1, 94, 48, 6, 74, 40, 17, 81, 119, 3, 28, 2, 45, 75, 122, 126, 105, 107, 96, 36, 115, 71, 125, 64, 0, 41, 70, 9, 117, 92, 121, 7,
27, 95, 111, 78, 26, 16, 85, 104, 58, 8, 82, 124, 113, 18, 79, 99, 97, 88, 11, 24, 109, 108, 52, 46, 110, 93, 43, 30, 86, 37, 87, 31, 118, 62, 35, 38, 77, 14, 51, 47, 55, 57,20, 89, 69, 65, 39, 101, 103, 15, 60, 44, 102, 73, 23, 90, 22, 91, 13, 98, 120, 25, 19, 50, 112, 56, 42, 5, 123, 53, 127, 80, 32, 49, 34, 54, 61, 84, 83, 100, 33, 12, 114, 4, 21, 72, 116, 63, 68, 106, 67]
B = [64, 58, 59, 7, 49, 95, 141, 175, 31, 115, 45, 215, 226, 154, 250, 149, 182, 135, 187, 70, 114, 120, 105, 88, 15, 234, 18, 89, 216, 176, 75, 251, 97,
166, 46, 78, 225, 35, 124, 203, 252, 86, 138, 169, 196, 199, 238, 158, 171, 102, 177, 60, 100, 72, 82, 143, 13, 181, 210, 43, 159, 65, 222, 173, 101,
93, 168, 39, 185, 69, 79, 17, 198, 2, 61, 37, 218, 243, 133, 52, 213, 245, 4, 111, 121, 255, 20, 233, 76, 117, 40, 118, 19, 128, 241, 132, 244, 178, 62,
116, 206, 51, 148, 80, 211, 142, 204, 74, 209, 21, 230, 162, 130, 25, 190, 106, 108, 5, 249, 92, 29, 83, 155, 11, 205, 57, 248, 253]
C = [73, 82, 117, 3, 123, 56, 24, 71, 26, 92, 86, 109, 113, 120, 8, 37, 75, 67, 90, 59, 10, 34, 4, 101, 79, 125, 1, 2, 51, 74, 98, 0, 61, 69, 19, 53, 107,
30, 88, 35, 70, 103, 54, 121, 41, 23, 27, 119, 65, 5, 32, 52, 64, 49, 22, 115, 116, 83, 20, 9, 99, 89, 91, 21, 84, 38, 93, 112, 95, 78, 17, 42, 6, 105, 55, 102, 15, 13, 122, 47, 60, 111, 33, 66, 43, 48, 63, 7, 29, 50, 97, 57, 16, 68, 18, 114, 44, 72, 45, 39, 106, 124, 100, 108, 58, 104, 80, 11, 28, 76, 62, 36, 12, 110, 87, 25, 46, 94, 77, 96, 81, 126, 118, 14, 31, 40, 127, 85]
D = []
for i in C:
D.append(B[i])
print(D) # 输出升序数列
4，由IDA分析到两重循环调用未知指令流，就知道要填写的代码仅仅是：if (比较){交换;} i++;（两重循环也是排序的特征，想到这个甚至可以跳过1、2、3步）
5，正确答案选取的是笔者认为最直接的思路，只要排序成功都能看到鼓励性输出。
6，笔者提供了自动机枚举答案的变体24640种，这些变体的大多数变体是有效但反人类的编程方式。笔者相信大多数人不需要机器枚举。
python程序只给了5个数据，原题是128个。不过，这完全不影响解法和解空间。
7，数学证明和编写思路见python程序的注释。
下面python程序正式开始：（附件是缩进良好的源代码，帖子本身难以保证缩进，诸君见谅！）
# WP By Totoro 大龙猫
# GOAL: sort the g_box
g_box = [2, 1, 3, 5, 4]
defrecover_box():
global g_box
g_box = [2, 1, 3, 5, 4]
# The followings are the test functions. Our goal is to make function "test" return True!
defsort_wrapper(func, *args):
global g_box
global g_i
loop =1
while loop <5:
g_i =1
while g_i <5:
func(*args) # this is the user input
loop = loop +1
result = g_box.copy()
for i inrange(0, 5):
result[i] = g_box[g_a[i]]
return result
deftest(func, *args):
if sort_wrapper(func, *args) != [1, 2, 3, 4, 5]:
returnFalse
returnTrue
# The following is the description of the virtual machine I designed.
# virtual registers
g_i =1
g_value =0
g_op =0
g_op1 =0
g_op2 =0
g_less_than =0
g_a = [4, 2, 1, 0, 3]
# macros
OP_ADD =0
OP_SUB =1
OP_AND =2
OP_OR =3
OP_XOR =4
OP_TEST =5
OP_MAX =6
# virtual instructions
definc():
global g_i
g_i = g_i +1
defdec():
global g_i
g_i = g_i -1
defset_op1():
global g_op1
g_op1 = g_value
defset_op2():
global g_op2
g_op2 = g_value
defload_value_i():
global g_value
g_value = g_i
defload_value_mem():
global g_value
g_value = g_a[g_value]
defload_value_box():
global g_value
g_value = g_box[g_value]
defload_op(op):
global g_op
g_op = op
defreset():
global g_less_than
g_less_than =True
defcontitional_calculate():
global g_less_than
if g_less_than:
if g_op == OP_ADD:
g_a[g_op1] += g_a[g_op2]
if g_op == OP_SUB:
g_a[g_op1] -= g_a[g_op2]
if g_op == OP_AND:
g_a[g_op1] &= g_a[g_op2]
if g_op == OP_OR:
g_a[g_op1] |= g_a[g_op2]
if g_op == OP_XOR:
g_a[g_op1] ^= g_a[g_op2]
if g_op == OP_TEST:
if g_op1 < g_op2:
g_less_than =True
elif g_op1 == g_op2:
g_less_than =False
elif g_op1 > g_op2:
g_less_than =False
# The design of the virtual machine ends.
# The cracking procedures is below.
# Here is a simple algorithm which costs about 32 bytes in virtual instructions.
defsimple_sort_kernel():
global g_i
global g_a
global g_box
g_i = g_i -1
if g_box[g_a[g_i]] > g_box[g_a[g_i +1]]:
temp = g_a[g_i]
g_a[g_i] = g_a[g_i +1]
g_a[g_i +1] = temp
g_i = g_i +2
# The simple answer needs following upper layer operations, in other words, virtual instructions groups
defload_box_value(): # 3 bytes, we finally use the unpacked version
load_value_i()
load_value_mem()
load_value_box()
defload_array_value(): # 2 bytes, we use the unpacked version
load_value_i()
load_value_mem()
defsave_value_to_op1(): # 1 byte, this operation is atomic
set_op1()
defsave_value_to_op2(): # 1 byte, this operation is atomic
set_op2()
# FIXED means that the instruction cannot be placed after the following FIXED instruction or ahead of the previous FIXED instruction.
# FREE means not FIXED
# The FIXED are both determined by the required function and the minimal size.
defbasic_compare(): # 13 bytes, this operation is not atomic, and has varians, but in minimal size using greedy algorithm.
# Since g_less_than == True is needed for g_box[g_a[op1]] > g_box[g_a[op2]], which makes "exchange" necessary, we have op1 = g_i + 1, op2 = g_i.
# Here op1 is set first, because g_i starts with 1, witch is the second unit of the array.
# of cource one may set op1 first, thus generates variants
load_box_value() # 3 bytes, FIXED
save_value_to_op1() # 1 byte, FIXED
dec() # 1 byte, FIXED
load_box_value() # 3 bytes, FIXED
save_value_to_op2() # 1 byte, FIXED
reset() # 1 byte, FREE, g_less_than == True is necessary for entering any arithmatic operations including the compare operation
load_op(OP_TEST) # 2 bytes, FREE, it can be moved ahead
contitional_calculate() # 1 byte, FIXED
# the load_box_value of basic_compare can be unpacked, so we use the "compare" function below.
defcompare(): # 13 bytes, this operation is not atomic, and has varians, but in minimal size using greedy algorithm.
# Since g_less_than == True is needed for g_box[g_a[op1]] > g_box[g_a[op2]], which makes "exchange" necessary, we have op1 = g_i + 1, op2 = g_i.
# Here op1 is set first, because g_i starts with 1, witch is the second unit of the array.
# of cource one may set op1 first, thus generates variants
load_value_i() # 1 bytes, FIXED
load_value_mem() # 1 bytes, FIXED
load_value_box() # 1 bytes, FIXED
save_value_to_op1() # 1 byte, FIXED
dec() # 1 byte, FIXED
load_value_i() # 1 bytes, FIXED
load_value_mem() # 1 bytes, FIXED
load_value_box() # 1 bytes, FIXED
save_value_to_op2() # 1 byte, FIXED
reset() # 1 byte, FREE, g_less_than == True is necessary for entering any arithmatic operations including the compare operation
load_op(OP_TEST) # 2 bytes, FREE, it can be moved ahead
contitional_calculate() # 1 byte, FIXED
# As we have 2 FREE instruction, which cannot be moved behind the contitional_calculate().
# These 2 FREE instruction has aterable relative orders.
# We have 10 * 11 = 110 variants generated by compare()
defexchange(): # 18 bytes, this operation is not atomic, and has varians, but in minimal size using greedy algorithm.
load_op(OP_XOR) # 2 bytes, FREE, set operation type, it can be downwards
# Of cource in the following blocks, one can set op2 ahead of op1, thus generates 2 * 2 * 2 = 8 variants
load_value_i() # 1 byte, FIXED, g_value = g_i
save_value_to_op1() # 1 byte, FIXED, op1 = g_value
inc() # 1 byte, FREE, g_i = g_i + 1
load_value_i() # 1 byte, FIXED, g_value = g_i
save_value_to_op2() # 1 byte, FIXED, op2 = g_i
contitional_calculate() # 1 byte, FIXED, a[op1] ^= a[op2], which means, a[i] ^= a[i + 1]
save_value_to_op1() # 1 byte, FIXED, op1 = g_value
dec() # 1 byte, FREE, g_i = g_i - 1
load_value_i() # 1 byte, FIXED, g_value = g_i
save_value_to_op2() # 1 byte, FIXED, op2 = g_value
contitional_calculate() # 1 byte, FIXED, a[op2] ^= a[op1], which means, a[i + 1] ^= a[i]
save_value_to_op1() # 1 byte, FIXED, op1 = g_value
inc() # 1 byte, FREE, g_i = g_i + 1
load_value_i() # 1 byte, FIXED, g_value = g_i
save_value_to_op2() # 1 byte, FIXED, op2 = g_value
contitional_calculate() # 1 byte, FIXED, a[op1] ^= a[op2], a[i] ^= a[i + 1]
# In the function "exchange" we have 4 FREE instruction.
# load_op(OP_XOR) can't be put behind or in front of contitional_calculate().
# Neither of inc or dec can be put behind or in front of load_value_i().
# We have amplified the number of the valid cases by a multiplier of 7 because of load_op(OP_XOR).
# We have amplified the number of the valid cases by a multiplier of 2 * 4 * 4 = 32 because of the other 3 FREE instructions
# The answer must contains compare, exchange, and an extra g_i++ for next loop, whose minimum size is 13 + 18 + 1 = 32
# The limited size is 32, so no extra bytes are free and the FIXED is realy fixed!
# So we have 110 * 7 * 32 = 24640 variants.
# Above all, that the space of the answers is very limited is PROVED!
# Here, we use the upper operations to build a default sort kernel, which can be mapped into virtual instructions
defdefault_sort_kernel():
compare()
exchange()
inc()
# Let's test the algorithm!
print(test(default_sort_kernel))
# We get a True! This VERY NORMAL algorithm is the answer to my quiz~
# We get a True! This VERY NORMAL algorithm is the answer to my quiz~
# We get a True! This VERY NORMAL algorithm is the answer to my quiz~
# The following is the robot program seeking for other answers.
# As the analysis above, we got 6 FREE instructions.
defload_op_test():
load_op(OP_TEST)
# Build all possible "compare" functions
# load_op_test, reset to be added
compare_sequence_base = [load_value_i, load_value_mem, load_value_box, save_value_to_op1, dec, load_value_i, load_value_mem, load_value_box, save_value_to_op2, contitional_calculate]
compare_sequence_list = []
for i inrange(0, 10):
for j inrange(0, 11):
compare_sequence = compare_sequence_base.copy()
compare_sequence.insert(i, load_op_test)
compare_sequence.insert(j, reset)
compare_sequence_list.append(compare_sequence)
# compare_sequence_list is the collection of
defadvanced_compare(compare_sequence):
for i in compare_sequence:
i()
defsort_kernel_of_free_sequence_v1(compare_sequence):
advanced_compare(compare_sequence)
exchange()
inc()
# use the following codes to validate the list
#for i in compare_sequence_list:
# print(test(sort_kernel_of_free_sequence_v1, i))
# recover_box()
defload_op_xor():
load_op(OP_XOR)
# load_op_xor, inc, dec, inc to be added
exchange_sequence_base = [load_value_i, save_value_to_op1, load_value_i, save_value_to_op2, contitional_calculate, \
save_value_to_op1, load_value_i, save_value_to_op2, contitional_calculate, \
save_value_to_op1, load_value_i, save_value_to_op2, contitional_calculate]
exchange_sequence_list = []
for i inrange(0, 7):
for j inrange(9, 13):
for k inrange(4, 8):
for l inrange(1, 3):
exchange_sequence = exchange_sequence_base.copy()
exchange_sequence.insert(l, inc)
exchange_sequence.insert(k, dec)
exchange_sequence.insert(j, inc)
exchange_sequence.insert(i, load_op_xor)
exchange_sequence_list.append(exchange_sequence)
defadvanced_exchange(exchange_sequence):
for i in exchange_sequence:
i()
defsort_kernel_of_free_sequence_v2(compare_sequence, exchange_sequence):
advanced_compare(compare_sequence)
advanced_exchange(exchange_sequence)
inc()
for i in compare_sequence_list:
for j in exchange_sequence_list:
print(test(sort_kernel_of_free_sequence_v2, i, j))
recover_box()
print('Total Count:', len(compare_sequence_list) *len(exchange_sequence_list))
# With compare_sequence_list and exchange_sequence_list, we get all valid sequences!
阿里云助力开发者！2核2G 3M带宽不限流量！6.18限时价，开 发者可享99元/年，续费同价！
|
|
|---|---|
