Posts

1pwnch

Amortized analysis

Why we need amortized analysis?

We always use worst case analysis (big-O) to calculate time complexity. However, have you ever thought that we would overestimate the cost? In specific algorithm, there is a sequence of operations with different costs. You might said that time complexity would be number of operations * the largest cost of operations. For example, there are three kinds of operations for stack: push, pop, and multipop(n) which would pop out n elements. Based on knowledge of worst case analysis, the ith operation takes O(n) of time complexity in worst case, then the sequence of n operations takes O(n^2) time. But how if there is only one O(n) and the rest of them are all O(1)? We have overestimate the cost of the case! Now, we know that the worst case bound is not tight because the expensive operation might not occur frequently. In amortized analysis, if sequence of operations have different costs, we can distribute the high one to the low ones. Following sections are three methods of amortized analysis.

Make it Generic

Introduction

Since Java 5, generic type has become significant part of Java. Why should we prefer generic type to raw type? Before arise of generic type, we need to convert the type of elements while reading them in collection. However, if the conversion fails, it would cause to runtime error. With generic type, we can tell compiler what type should be limited for collection in advance. If there exists an error, get compiler error before it becomes a runtime error is much better, isn’t it?

Conversion from mutable to immutable class

Introduction

When it comes to immutability of java, it’s important for us to know about data type of String. Each time we try to modify the string, it would create a new object with new value. When it comes to mutability of java, the sample data type for it would be such like array, and we can modify the elements on specific index. However, it is a more interesting topic in this article: How to create an immutable class by ourselves?

Analysis and Mitigation of CVE-2018-13379

Introduction

In CVE-2018-13379, untrusted user could use the feature of snprintf() to launch the attack of arbitrary file reading.
Isn’t snprintf() already a safer function?
What kind of the feature can be used to bypass the limitation of file extension?
In this article, I would not only analyze the way of launching an attack, but also share some ideas of mitigation!