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。

相关文章

Java利用JSONPath操作JSON数据的技术指南

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath？3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4
阅读更多...
一文详解SpringBoot响应压缩功能的配置与优化

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML
阅读更多...
MySQL大表数据的分区与分库分表的实现

MySQL大表数据的分区与分库分表的实现

《MySQL大表数据的分区与分库分表的实现》数据库的分区和分库分表是两种常用的技术方案,本文主要介绍了MySQL大表数据的分区与分库分表的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有... 目录1. mysql大表数据的分区1.1 什么是分区？1.2 分区的类型1.3 分区的优点1.4 分
阅读更多...
Mysql删除几亿条数据表中的部分数据的方法实现

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T
阅读更多...
Python Dash框架在数据可视化仪表板中的应用与实践记录

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash？1.1
阅读更多...
Redis 中的热点键和数据倾斜示例详解

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键（Hot Key）定义特点应对策略示例数据倾斜（Data S
阅读更多...
Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录，并压缩为zip文件到另一个
阅读更多...
SpringBoot整合jasypt实现重要数据加密

SpringBoot整合jasypt实现重要数据加密

《SpringBoot整合jasypt实现重要数据加密》Jasypt是一个专注于简化Java加密操作的开源工具,：本文主要介绍详细介绍了如何使用jasypt实现重要数据加密,感兴趣的小伙伴可... 目录jasypt简介 jasypt的优点SpringBoot使用jasypt创建mapper接口配置文件加密
阅读更多...
使用Python高效获取网络数据的操作指南

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解
阅读更多...
Oracle存储过程里操作BLOB的字节数据的办法

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2