Search for: All records

In recent years, many different cryptocurrencies have risen in popularity. Since coins vary in fiat value and functionality, it has become important to securely exchange between them. A common exchange method is hashed timelock contracts (HTLC). However, this method did not support brokerage transactions that allow parties to leverage assets they gain during the transaction. We consider HTLC with brokering. The transaction fees for HTLC is a direct function of the size of the leader set. Thus, brokers are interested in finding the minimum leader set of a given transaction graph. We show that finding the minimum leader set on general transaction graphs with brokering is NP-hard. We then introduce flower transaction graphs, a common type of transaction graphs with brokering, and show that finding the minimum leader set of a flower graph is also NP-hard through a reduction from the knapsack problem. 

Memory errors are one of the most common vulnerabilities for the popularity of memory unsafe languages including C and C++. Once exploited, it can easily lead to system crash (i.e., denial-of-service attacks) or allow adversaries to fully compromise the victim system. This paper proposes MEDS, a practical memory error detector. MEDS significantly enhances its detection capability by approximating two ideal properties, called an infinite gap and an infinite heap. The approximated infinite gap of MEDS setups large inaccessible memory region between objects (i.e., 4 MB), and the approximated infinite heap allows MEDS to fully utilize virtual address space (i.e., 45-bits memory space). The key idea of MEDS in achieving these properties is a novel user-space memory allocation mechanism, MEDSALLOC. MEDSALLOC leverages a page aliasing mechanism, which allows MEDS to maximize the virtual memory space utilization but minimize the physical memory uses. To highlight the detection capability and practical impacts of MEDS, we evaluated and then compared to Google’s state-of-the-art detection tool, AddressSanitizer. MEDS showed three times better detection rates on four real-world vulnerabilities in Chrome and Firefox. More importantly, when used for a fuzz testing, MEDS was able to identify 68.3% more memory errors than AddressSanitizer for the same amount of a testing time, highlighting its practical aspects in the software testing area. In terms of performance overhead, MEDS slowed down 108% and 86% compared to native execution and AddressSanitizer, respectively, on real-world applications including Chrome, Firefox, Apache, Nginx, and OpenSSL.