An implementation of external memory efficient, cpu instruction and memory access trace oblivious sorting algorithms.
Install cmake, ninja and intel sgx sdk, or use the cppbuilder docker image. Requires x64 architecture (Apple M series CPU not supported).
docker build -t cppbuilder:latest ./tools/docker/cppbuilderdocker run -v /tmp/sortbackend:/ssdmount --privileged -it --rm -v $PWD:/builder cppbuilderrm -rf build # optional
export CC=/usr/bin/clang
export CXX=/usr/bin/clang++
cmake -B build -G Ninja -DCMAKE_BUILD_TYPE=Release
ninja -C buildRun the scripts below, or use tools such as C++ TestMate in vscode.
Warning: 1TB RAM required to run the full benchmarks presented in the paper. When benchmarking each algorithm, the input size N increases incrementally, and a C++ exception with description "std::bad_alloc" may be thrown in the test body when the RAM becomes insufficient. Consider adjusting the range of N in perf_sort.cpp and run each benchmark individually.
./build/tests/test_basic_perf --gtest_filter=*TestSortInternalIncr*Sort*To test the results for different element sizes, change line 14 of file osort/external_memory/algorithm/sort_def.hpp and rebuild (i.e., #define ELEMENT_SIZE 128)
./build/tests/test_basic_perf --gtest_filter=*TestSortInternal1e8*Sort*./build/tests/test_basic_perf --gtest_filter=*TestSortInternalIncr*Shuffle*To test the results for different element sizes, change line 14 of file osort/external_memory/algorithm/sort_def.hpp and rebuild (i.e., #define ELEMENT_SIZE 128)
./build/tests/test_basic_perf --gtest_filter=*TestSortInternal1e8*Shuffle*./build/tests/test_appsWe provide a script algo_runner.sh for benchmarking algorithms in SGX. Modify the script as needed to test different scenes. The script outputs result to a text file by default.
cd applications/sorting
./algo_runner.sh
# to output the terminal, run ./algo_runner.sh 1osort - C++ osort library code
tests - C++ tests modules
applications - Enclaves example of osort
tools - tools used to generate graphs or test sets
tools/docker - dockerfiles used for reproducible builds
common - common c++ utilies, cpu abstractions, cryptography abstractions and tracing code
external_memory - external memory abstraction and sorting algorithms
external_memory/server - server abstraction for different external memory scenarios (sgx, file system, ram)