zstd字典压缩的大数据生产实践 ctf逆向出题启发

本文主要是介绍zstd字典压缩的大数据生产实践 ctf逆向出题启发，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

zstd实践
命题思路
rust背景
rust的一些特征
rust的异常处理
具体算法逻辑
算法理解
妥协
代码

zstd实践

首先明确，所有的压缩，和不压缩比，都是cpu换带宽/硬盘。
按我对教科书huffman编码和lzma算法的了解，他们都适合对大文件的压缩，基本原理都是“给高频pattern最短路”。
数据库/数据流压缩，情景不同。操作的对象是许许多多的单行（小文件），而非一个大文件。这导致行与行之间的重复内容无法复用。
zstd可以提前编译字典，字典可以定制化。
在我们的业务数据上，能节省35%的CPU，压缩率提升63%。代价是维护字典，所以适合内网使用（否则需要客户端也参与字典的版本维护），比如我们自己跨AZ的数据搬运。

在一定范围内，字典越大，压缩越慢，压缩率越高，也需要配合更高的压缩等级。字典的体积在100k-500k之间，一般不超过1M。

zstd这个字典也有训练和测试的说法，这个不难理解。构造一个接近实际数据的字典才能有好的压缩效果。好比我们的操作手册，肯定得记录我们自己实际遇到的问题，查询的时候才能较好命中。

gzip比较老，而且是单线程的。pigz是gzip的多线程版。zstd是facebook在2016发布的，自然是支持多线程。spark从3.0开始支持ZSTD，对比默认的snappy，压缩率可以提升30%，降低存储和传输成本。

当然，刚刚提及的所有压缩算法，对hash值这种都没法压缩，因为hash的灵魂就是防碰撞，每个都是低频。hash的压缩需要考虑其它原理的方法。

命题思路

一方面是初次接触rust，一方面是实现一个类似zstd的算法。
命题思路上，我会写两个rust编译后生成的可执行程序，一个用于压缩，一个用于解压缩。
公开放出的是压缩可执行程序，字典，压缩结果。
验题时使用解压缩可执行程序，字典，压缩结果。
题目难点将是，陌生的语言，以及并无现成代码。
给输出求输入的模式，避免了flag在执行过程中在内存里出现。
flag长度准备弄长一点，避免强制破解。

rust背景

Rust 语言可以用于开发：
传统命令行程序 - Rust 编译器可以直接生成目标可执行程序，不需要任何解释程序。
Web 应用 - Rust 可以被编译成 WebAssembly，WebAssembly 是一种 JavaScript 的高效替代品。
网络服务器 - Rust 用极低的资源消耗做到安全高效，且具备很强的大规模并发处理能力。
嵌入式设备 - Rust 同时具有JavaScript的开发速度和 C 语言的执行效率，支持底层平台的开发。

编译器，rustc。
包管理，cargo。

rust的一些特征

导入用的是use，print用的是println!。
函数尾部不带分号，隐式return此表达式。
match关键字作用类似switch。

rust的异常处理

rust函数往往返回一个复合的result类型，它里面的内容可能是好消息，也可能是坏消息。
一句话一般来说以分号结尾，在分号之前加上一个问号，其实是一种match的简写，如果ok就正常返回，如果报错就返回error。
unwrap()也是异常处理，相当于把result解包，如果ok就会返回正常结果，如果出错，就panic崩溃。

具体算法逻辑

本来想自己实现zstd，
发现有点复杂，而且二手资料很少，感觉不值当。
http://www.ezcodesample.com/abs/abs_article.html
上面的链接介绍了ANS，asymmetric numeral system。zstd基于它实现。
这个链接的复杂度更适合出题。

算法理解

出现频率高的，在码表中的行数比较多，输出的bit数就少。
这一点和huffman的思路倒是很像。

精度和码表大小的关系：
码表的构造和frequency高度相关，如果想让frequency很精确的话，码表就要足够大。

妥协

上面的英文链接里有C语言实现，但我肯定不想直接用那个。
自己写的算法，解压时发现不可逆，可以有两种fetch方法。
所以我在想重新设计一下算法，使之更加简化。

每次输出时都加校验码，表示这次输出几bit。恐怕已经不能再称之为“压缩”，不过作为题目没关系。

代码

上面是编码，下面是解码。

use std::fmt::format;
use std::fs;
use std::io::Write;
use fs::File;fn main() -> Result<(), std::io::Error>{let array_a: [usize; 14] = [2,4,7,9,12,13,16,18,19,23,24,27,29,31];let array_b: [usize; 10] = [3,6,8,11,14,17,21,22,26,28];let array_c: [usize; 6] = [5,10,15,20,25,30];let flag_path: &str = "flag.txt";let flag = fs::read_to_string(flag_path);// println!("Data read: {:?}", flag);let mut state: usize= 31;let mut binary_string = String::new();let mut bit_string: String;for c in flag?.chars() {println!("before:{}", state);let cur_len: usize;let outputbit: &str;let outputlen: String;let head_two: usize = state >> 3;let head_three: usize = state >> 2;let head_four: usize = state >> 1;bit_string = format!("{:b}", state);if bit_string.len() < 5 {bit_string = format!("{}{}", '0'.to_string().repeat(5-bit_string.len()), bit_string);// println!("padding!");}let bit_str: &str = &bit_string.as_str();match c {'a' => cur_len = 14,'b' => cur_len = 10,'c' => cur_len = 6,_ => cur_len = 99999}if state > cur_len {if head_four <= cur_len {state = head_four;outputbit = &bit_str[4..];outputlen = format!("01");}else if head_three <= cur_len {state = head_three;outputbit = &bit_str[3..];outputlen = format!("10");}else {state = head_two;outputbit = &bit_str[2..];outputlen = format!("11");}println!("output bits:{}", outputbit);binary_string.push_str(outputbit);binary_string = format!("{}{}", binary_string, outputlen);}else {outputlen = format!("00");binary_string = format!("{}{}", binary_string, outputlen);}println!("after output:{}", state);match c {'a' => state = array_a[state - 1],'b' => state = array_b[state - 1],'c' => state = array_c[state - 1],_ => ()}}bit_string = format!("{:b}", state);if bit_string.len() < 5 {bit_string = format!("{}{}", '0'.to_string().repeat(5-bit_string.len()), bit_string);// println!("padding!");}println!("last state {}", state);println!("last state {}", bit_string);binary_string = format!("{}{}", binary_string, bit_string);println!("{}", binary_string);let mut byte_array: Vec<u8> = vec![binary_string.len() as u8];let mut content: Vec<u8> = binary_string.as_bytes().chunks(8).map(|chunk| {let bit_str = std::str::from_utf8(chunk).unwrap();u8::from_str_radix(bit_str, 2).unwrap()}).collect();byte_array.append(&mut content);println!("{:?}", byte_array);let mut file = File::create("output")?;file.write_all(&byte_array)?;file.flush()?;Ok(())
}

use std::fs;
use std::fs::File;
use std::io::{self, Read};fn main() -> io::Result<()>{let mut file = File::open("output")?;let mut buffer: Vec<u8> = Vec::new();file.read_to_end(&mut buffer)?;// println!("File content as bytes: {:?}", buffer);let length: usize = buffer[0] as usize;// println!("length of initial bit stream: {}", length);let mut binary_string: String = String::new();for i in 1..buffer.len() {let mut byte_string: String = format!("{:b}", buffer[i]);if i < buffer.len() - 1 && byte_string.len() < 8 {let pad: String = '0'.to_string().repeat(8-byte_string.len());byte_string = format!("{}{}", pad, byte_string);// println!("padding!");}if i == buffer.len() - 1 {let pad: String = '0'.to_string().repeat(length - binary_string.len() - byte_string.len());byte_string = format!("{}{}", pad, byte_string);}binary_string.push_str(byte_string.as_str());}println!("initial binary string: {}", binary_string);assert_eq!(binary_string.len(), length, "The decoded binary string does not have the expected length.");let array_a: [usize; 14] = [2,4,7,9,12,13,16,18,19,23,24,27,29,31];let array_b: [usize; 10] = [3,6,8,11,14,17,21,22,26,28];let array_c: [usize; 6] = [5,10,15,20,25,30];let mut res: String = String::new();let mut state_str: String = binary_string[binary_string.len()-5..binary_string.len()].to_string();binary_string = binary_string[0..binary_string.len()-5].to_string();let mut state: usize = u8::from_str_radix(state_str.as_str(), 2).unwrap() as usize;while binary_string.len() > 0 {// println!("state: {}, state_str:{}, binary string: {}", state, state_str, binary_string);let mut symbol: char = ' ';if let Some(index) = array_a.iter().position(|&x| x == state) {symbol = 'a';state = index + 1;}else if let Some(index) = array_b.iter().position(|&x| x == state) {symbol = 'b';state = index + 1;}else if let Some(index) = array_c.iter().position(|&x| x == state) {symbol = 'c';state = index + 1;}else {println!("Error, not found in table, {}", state);break;}state_str = format!("{:b}", state);let mut fetch_string: String = String::new();if state_str.len() < 5 {// fetch几个？let fetch_num: usize = u8::from_str_radix(&binary_string[binary_string.len()-2..], 2).unwrap() as usize;binary_string = binary_string[0..binary_string.len()-2].to_string();fetch_string = binary_string[(binary_string.len()-fetch_num)..binary_string.len()].to_string();if fetch_num < 5 - state_str.len() {state_str = format!("{}{}{}", '0'.to_string().repeat(5 - state_str.len() - fetch_num), state_str, fetch_string);}else {state_str = format!("{}{}", state_str, fetch_string);}binary_string = binary_string[0..binary_string.len()-fetch_num].to_string();}if state_str.len() != 5 {println!("state_str {}, fetch_string {}", state_str, fetch_string);}println!("symbol:{}, state:{}, fetch string:{}", symbol, state, fetch_string);state = u8::from_str_radix(state_str.as_str(), 2).unwrap() as usize;res.push(symbol as char);}let reversed_res: String = res.chars().rev().collect();println!("{}", reversed_res);Ok(())
}