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

2024-02-07 16:04
文章标签 数据 ctf 压缩 逆向 字典 出题 生产实践 zstd 启发

本文主要是介绍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(())
}

这篇关于zstd字典压缩的大数据生产实践 ctf逆向出题启发的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/688229。

相关文章

Python在二进制文件中进行数据搜索的实战指南

Python在二进制文件中进行数据搜索的实战指南

《Python在二进制文件中进行数据搜索的实战指南》在二进制文件中搜索特定数据是编程中常见的任务,尤其在日志分析、程序调试和二进制数据处理中尤为重要,下面我们就来看看如何使用Python实现这一功能吧... 目录简介1. 二进制文件搜索概述2. python二进制模式文件读取（rb）2.1 二进制模式与文本
阅读更多...
C#实现将XML数据自动化地写入Excel文件

C#实现将XML数据自动化地写入Excel文件

《C#实现将XML数据自动化地写入Excel文件》在现代企业级应用中,数据处理与报表生成是核心环节,本文将深入探讨如何利用C#和一款优秀的库,将XML数据自动化地写入Excel文件,有需要的小伙伴可以... 目录理解XML数据结构与Excel的对应关系引入高效工具：使用Spire.XLS for .NETC
阅读更多...
MySQL数据目录迁移的完整过程

MySQL数据目录迁移的完整过程

《MySQL数据目录迁移的完整过程》文章详细介绍了将MySQL数据目录迁移到新硬盘的整个过程,包括新硬盘挂载、创建新的数据目录、迁移数据（推荐使用两遍rsync方案）、修改MySQL配置文件和重启验证... 目录1，新硬盘挂载（如果有的话）2，创建新的 mysql 数据目录3，迁移 MySQL 数据（推荐两
阅读更多...
Python数据验证神器Pydantic库的使用和实践中的避坑指南

Python数据验证神器Pydantic库的使用和实践中的避坑指南

《Python数据验证神器Pydantic库的使用和实践中的避坑指南》Pydantic是一个用于数据验证和设置的库,可以显著简化API接口开发,文章通过一个实际案例,展示了Pydantic如何在生产环... 目录1️⃣ 崩溃时刻：当你的API接口又双叒崩了！2️⃣ 神兵天降：3行代码解决验证难题3️⃣ 深度
阅读更多...
MySQL快速复制一张表的四种核心方法(包括表结构和数据)

MySQL快速复制一张表的四种核心方法(包括表结构和数据)

《MySQL快速复制一张表的四种核心方法(包括表结构和数据)》本文详细介绍了四种复制MySQL表（结构+数据）的方法,并对每种方法进行了对比分析,适用于不同场景和数据量的复制需求,特别是针对超大表（1... 目录一、mysql 复制表（结构+数据）的 4 种核心方法（面试结构化回答）方法 1：CREATE
阅读更多...
详解C++ 存储二进制数据容器的几种方法

详解C++ 存储二进制数据容器的几种方法

《详解C++存储二进制数据容器的几种方法》本文主要介绍了详解C++存储二进制数据容器,包括std::vector、std::array、std::string、std::bitset和std::ve... 目录1.std::vector<uint8_t>（最常用）特点：适用场景：示例：2.std::arra
阅读更多...
MySQL中的DELETE删除数据及注意事项

MySQL中的DELETE删除数据及注意事项

《MySQL中的DELETE删除数据及注意事项》MySQL的DELETE语句是数据库操作中不可或缺的一部分,通过合理使用索引、批量删除、避免全表删除、使用TRUNCATE、使用ORDERBY和LIMI... 目录1. 基本语法单表删除2. 高级用法使用子查询删除删除多表3. 性能优化策略使用索引批量删除避免
阅读更多...
MySQL 数据库进阶之SQL 数据操作与子查询操作大全

MySQL 数据库进阶之SQL 数据操作与子查询操作大全

《MySQL数据库进阶之SQL数据操作与子查询操作大全》本文详细介绍了SQL中的子查询、数据添加（INSERT）、数据修改（UPDATE）和数据删除（DELETE、TRUNCATE、DROP）操作... 目录一、子查询：嵌套在查询中的查询1.1 子查询的基本语法1.2 子查询的实战示例二、数据添加：INSE
阅读更多...
Linux服务器数据盘移除并重新挂载的全过程

Linux服务器数据盘移除并重新挂载的全过程

《Linux服务器数据盘移除并重新挂载的全过程》：本文主要介绍在Linux服务器上移除并重新挂载数据盘的整个过程,分为三大步：卸载文件系统、分离磁盘和重新挂载,每一步都有详细的步骤和注意事项,确保... 目录引言第一步：卸载文件系统第二步：分离磁盘第三步：重新挂载引言在 linux 服务器上移除并重新挂p
阅读更多...
使用MyBatis TypeHandler实现数据加密与解密的具体方案

使用MyBatis TypeHandler实现数据加密与解密的具体方案

《使用MyBatisTypeHandler实现数据加密与解密的具体方案》在我们日常的开发工作中,经常会遇到一些敏感数据需要存储,比如用户的手机号、身份证号、银行卡号等,为了保障数据安全,我们通常会对... 目录1. 核心概念：什么是 TypeHandler？2. 实战场景3. 代码实现步骤步骤 1：定义 E
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2