1 // Copyright 2016 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include <fbl/algorithm.h>
6 #include <fbl/array.h>
7 #include <fbl/auto_call.h>
8 #include <fbl/unique_ptr.h>
9 #include <fcntl.h>
10 #include <inttypes.h>
11 #include <lib/fdio/io.h>
12 #include <lib/fdio/spawn.h>
13 #include <limits.h>
14 #include <math.h>
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <sys/param.h>
19 #include <sys/stat.h>
20 #include <unistd.h>
21 
22 #include <zircon/process.h>
23 #include <zircon/processargs.h>
24 #include <zircon/process.h>
25 #include <zircon/syscalls.h>
26 #include <zircon/syscalls/object.h>
27 #include <zircon/types.h>
28 
29 struct ReportInfo {
30     uintptr_t exec_addr = 0;
31     uintptr_t first_stack = 0;
32     uintptr_t first_heap_alloc = 0;
33     uintptr_t libc = 0;
34     uintptr_t vdso = 0;
35 };
36 
37 namespace {
38 
39 static const char* kBinName = "/boot/bin/aslr-analysis";
40 
41 int GatherReports(const char* test_bin, fbl::Array<ReportInfo>* reports);
42 unsigned int AnalyzeField(const fbl::Array<ReportInfo>& reports,
43                           uintptr_t ReportInfo::*field);
44 double ApproxBinomialCdf(double p, double N, double n);
45 int TestRunMain(int argc, char** argv);
46 zx_status_t LaunchTestRun(const char* bin, zx_handle_t h, zx_handle_t* out);
47 int64_t JoinProcess(zx_handle_t proc);
48 } // namespace
49 
main(int argc,char ** argv)50 int main(int argc, char** argv) {
51     // TODO(teisenbe): This is likely too low; compute how many runs we
52     // will need for statistical confidence
53     static const int kNumRuns = 1000;
54 
55     if (argc > 1 && !strcmp(argv[1], "testrun")) {
56         return TestRunMain(argc, argv);
57     }
58 
59     struct stat stat_info;
60     if (stat(kBinName, &stat_info) != 0 || !S_ISREG(stat_info.st_mode)) {
61         printf("Could not find %s for running tests\n", kBinName);
62         return 1;
63     }
64 
65     fbl::Array<ReportInfo> reports(new ReportInfo[kNumRuns], kNumRuns);
66     if (!reports) {
67         printf("Failed to allocate reports\n");
68         return 1;
69     }
70 
71     int ret = GatherReports(kBinName, &reports);
72     if (ret != 0) {
73         return 1;
74     }
75     printf("Finished gathering reports\n");
76 
77     unsigned int bits;
78     bits = AnalyzeField(reports, &ReportInfo::exec_addr);
79     printf("exec_addr: %d bits\n", bits);
80     bits = AnalyzeField(reports, &ReportInfo::first_stack);
81     printf("first_stack: %d bits\n", bits);
82     bits = AnalyzeField(reports, &ReportInfo::first_heap_alloc);
83     printf("first_heap_alloc: %d bits\n", bits);
84     bits = AnalyzeField(reports, &ReportInfo::libc);
85     printf("libc: %d bits\n", bits);
86     bits = AnalyzeField(reports, &ReportInfo::vdso);
87     printf("vdso: %d bits\n", bits);
88 
89     return 0;
90 }
91 
92 namespace {
93 
94 // Computes P(X <= n), approximated via the normal distribution
ApproxBinomialCdf(double p,double N,double n)95 double ApproxBinomialCdf(double p, double N, double n) {
96     // https://en.wikipedia.org/wiki/Normal_distribution#Cumulative_distribution_function
97     // https://en.wikipedia.org/wiki/Binomial_distribution#Normal_approximation
98     const double mu = N * .5;
99     const double sigma = sqrt(N * .5 * .5);
100     // Note we add 1/2 to n below as a continuity correction.
101     return 0.5 * (1. + erf((n + .5 - mu) / (sigma * sqrt(2.))));
102 }
103 
104 // Perform an approximate two-sided binomial test across each bit-position for
105 // all of the reports.
106 //
107 // |reports| is an array of samples gathered from launching processes
108 //
109 // |field| is a pointer to the field that is being analyzed
110 //
111 // TODO: Investigate if there are better approaches than the two-sided binomial
112 // test.
113 // TODO: Do further analysis to account for potential non-independence of bits
AnalyzeField(const fbl::Array<ReportInfo> & reports,uintptr_t ReportInfo::* field)114 unsigned int AnalyzeField(const fbl::Array<ReportInfo>& reports,
115                           uintptr_t ReportInfo::*field) {
116     int good_bits = 0;
117 
118     const size_t count = reports.size();
119     for (unsigned int bit = 0; bit < sizeof(uintptr_t) * 8; ++bit) {
120         size_t ones = 0;
121         for (unsigned int i = 0; i < count; ++i) {
122             uintptr_t val = reports[i].*field;
123             if (val & (1ULL << bit)) {
124                 ones++;
125             }
126         }
127 
128         size_t n = ones;
129         // Since we're doing a two-tailed test, set n to be the left tail
130         // bound to simplify the calculation.
131         if (n > count / 2) {
132             n = count - n;
133         }
134 
135         // Probability that we'd see at most ones 1s or at least count/2 +
136         // (count/2 - ones) 1s (i.e., the two-sided probability).  Since p=.5,
137         // these two propabilities are the same.
138         //
139         // Note the normal approximation is valid for us, since we are dealing with
140         // p=0.5 and N > 9(1 - p)/p and N > 9p/(1-p) (a common rule of thumb).
141         const double p = 2 * ApproxBinomialCdf(0.5, static_cast<double>(count),
142                                                static_cast<double>(n));
143 
144         // Test the result against our alpha-value.  If p <= alpha, then the
145         // alternate hypothesis of a biased bit is considered true.  We choose
146         // alpha = 0.10, rather than the more conventional 0.05, to bias
147         // ourselves more towards false positives (considering a bit to
148         // be biased) rather than more false negatives.
149         if (p > 0.10) {
150             good_bits++;
151         }
152     }
153     return good_bits;
154 }
155 
GatherReports(const char * test_bin,fbl::Array<ReportInfo> * reports)156 int GatherReports(const char* test_bin, fbl::Array<ReportInfo>* reports) {
157     const size_t count = reports->size();
158     for (unsigned int run = 0; run < count; ++run) {
159         zx_handle_t handles[2];
160         zx_status_t status = zx_channel_create(0, &handles[0], &handles[1]);
161         if (status != ZX_OK) {
162             printf("Failed to create channel for test run\n");
163             return -1;
164         }
165 
166         zx_handle_t proc;
167         if ((status = LaunchTestRun(test_bin, handles[1], &proc)) != ZX_OK) {
168             zx_handle_close(handles[0]);
169             printf("Failed to launch testrun: %d\n", status);
170             return -1;
171         }
172 
173         int64_t ret = JoinProcess(proc);
174         zx_handle_close(proc);
175 
176         if (ret != 0) {
177             zx_handle_close(handles[0]);
178             printf("Failed to join testrun: %" PRId64 "\n", ret);
179             return -1;
180         }
181 
182         ReportInfo* report = &(*reports)[run];
183 
184         uint32_t len = sizeof(*report);
185         status = zx_channel_read(handles[0], 0, report, NULL, len, 0, &len, NULL);
186         if (status != 0 || len != sizeof(*report)) {
187             printf("Failed to read report: status %d, len %u\n", status, len);
188             zx_handle_close(handles[0]);
189             return -1;
190         }
191 
192         zx_handle_close(handles[0]);
193     }
194     return 0;
195 }
196 
TestRunMain(int argc,char ** argv)197 int TestRunMain(int argc, char** argv) {
198     zx_handle_t report_pipe =
199         zx_take_startup_handle(PA_HND(PA_USER1, 0));
200 
201     ReportInfo report;
202 
203     // TODO(teisenbe): Ideally we should get measurements closer to the source
204     // of the mapping rather than inferring from data locations
205     report.exec_addr = (uintptr_t)&main;
206     report.first_stack = (uintptr_t)&report_pipe;
207     report.first_heap_alloc = (uintptr_t)malloc(1);
208     report.libc = (uintptr_t)&memcpy;
209     report.vdso = (uintptr_t)&zx_channel_write;
210 
211     zx_status_t status =
212         zx_channel_write(report_pipe, 0, &report, sizeof(report), NULL, 0);
213     if (status != ZX_OK) {
214         return status;
215     }
216 
217     return 0;
218 }
219 
220 // This function unconditionally consumes the handle h.
LaunchTestRun(const char * bin,zx_handle_t h,zx_handle_t * proc)221 zx_status_t LaunchTestRun(const char* bin, zx_handle_t h, zx_handle_t* proc) {
222     const char* argv[] = {bin, "testrun", nullptr};
223 
224     fdio_spawn_action_t actions[2];
225     actions[0].action = FDIO_SPAWN_ACTION_SET_NAME;
226     actions[0].name.data = "testrun";
227     actions[1].action = FDIO_SPAWN_ACTION_ADD_HANDLE;
228     actions[1].h = {.id = PA_USER1, .handle = h};
229 
230     char err_msg[FDIO_SPAWN_ERR_MSG_MAX_LENGTH];
231     zx_status_t status = fdio_spawn_etc(ZX_HANDLE_INVALID, FDIO_SPAWN_DEFAULT_LDSVC, bin, argv,
232                                         nullptr, fbl::count_of(actions), actions, proc, err_msg);
233 
234     if (status != ZX_OK)
235         printf("launch failed (%d): %s\n", status, err_msg);
236 
237     return ZX_OK;
238 }
239 
JoinProcess(zx_handle_t proc)240 int64_t JoinProcess(zx_handle_t proc) {
241     zx_status_t status =
242         zx_object_wait_one(proc, ZX_PROCESS_TERMINATED, ZX_TIME_INFINITE, NULL);
243     if (status != ZX_OK) {
244         printf("join failed? %d\n", status);
245         return -1;
246     }
247 
248     // read the return code
249     zx_info_process_t proc_info;
250     if ((status = zx_object_get_info(proc, ZX_INFO_PROCESS, &proc_info,
251                                      sizeof(proc_info), NULL, NULL)) < 0) {
252         printf("handle_get_info failed? %d\n", status);
253         return -1;
254     }
255 
256     return proc_info.return_code;
257 }
258 
259 } // namespace
260