19 Haziran 2017 Pazartesi

Linear Least Squares Analysis

Giriş
Türkçesi sanırım "En Küçük Karaler Yöntemi". Nümerik Analiz dersinde en nefret ettiğim konulardan birisi. Kimin bu yöntemi geliştirdiğine dair bir açıklama şöyle
A fascinating point is that development of least squares came before the discovery of the normal distribution and modern justifications for the use of least squares.

Least squares was developed as a way of combining multiple, imperfect astronomical observations to recover underlying parameters governing the movements of heavenly bodies.

Each astronomical observation defines a linear equation, and with more observations than parameters, the astronomers of the time were faced with an inconsistent system. What to do? Mayer developed a method where observations were separated into kk groups, the equations in each group were averaged together, and then the underlying system could be solved (Stigler 1990). Legendre instead proposed introducing an error term and minimizing the sum of squared error. 

Sıkıştırma

Lossless Compression
Lossless compression algoritmaları her şeyi çok iyi sıkıştıramıyor. Açıklaması şöyle
There can be no algorithm that losslessly compresses all inputs. But there are many algorithms that losslessly compress many inputs. And it turns out that most of the strings we like to operate on have enough internal redundancy that they compress rather well.

Huffman Coding
Huffman Coding yazısına taşıdım.

Delta Compression
Delta Compression yazısına taşıdım.

LZW
LZW yazısına taşıdım.

GZip
GZip tek bir dosyayı sıkıştırır. Genellikle tar ile kullanılır. Tar önce bir arşiv oluşturur, daha sonra gzip bu arşivi sıkıştırır.

gzip komutu
gzip komutu yazısına taşıdım.

17 Haziran 2017 Cumartesi

TUN/TAP

Giriş
Linux üzerinde yaratılan TAP arayüzünden pcap ile okuma işlemi çalışıyor ancak yazma işlemi bir türlü olmadı. Sebebini bilmiyorum.

Windows üzerinde yaratılan TAP arayüzünden pcap ile okuma ve yazma işlemi sorunsuz çalışıyor.

Linux Komut Satırı
Sanal bir arayüz oluşturmak için kullanılabilir.
1. Önce arayüz oluşturulur
ip tuntap add mode tap myintf
veya şöyle yaparız. Ben bunu kullandım.
ip tuntap add dev myintf mode tap
2. Arayüzü ayağa kaldırırız.
ifconfig myintf up
veya şöyle yaparız. Ben bunu kullandım
ip link set myintf up
3. IP adresi atarız.
ip a a 192.168.1.1/24 dev myintf
Ben bunu kullandım
ip addr 10.0.0.1/24 dev myintf
IP adresi ve broadcast adresi atamak istersek şöyle yaparız.
ip addr add dev tap0 10.7.110.110/16 broadcast 10.7.255.255
Oluşan arayüz geçicidir. Kalıcı olması için /etc/network/interfaces dosyasına yazılması gerekir.
Ayrıca arayüz UP, BROADCAST olarak görünür ama RUNNING değildir. Bir yazılım ilk defa bu arayüze bağlanınca RUNNING olur. Yani ethernet kartına kablonun takılması gibi düşünülebilir.

Linux API
1. Yaratma
Hataları ele almayı gözardı edersek device şöyle yaratılır veya etkinleştirilir. Eğer tap arayüzü varsa ağ arayüzü etkinleşir. Yani arayüz RUNNING olur. Yoksa arayüz yaratılır. IFF_NO_PI bayrağı ile sadece ethernet paketlerini yakalarız. TAP bize fazladan byte'lar vermez.
char *dev = "myintf"
struct ifreq ifr;

char *clonedev = "/dev/net/tun";

//open the clone device
int fd = open(clonedev, O_RDWR);

//preparation of the struct ifr, of type "struct ifreq"
memset(&ifr, 0, sizeof(ifr));

ifr.ifr_flags = IFF_TAP | IFF_NO_PI;

strncpy(ifr.ifr_name, dev, IFNAMSIZ);

//try to create the device
ioctl(fd, TUNSETIFF, (void *) &ifr);

2. MAC Adresi Verme
struct ifreq ifr;
ifr.ifr_hwaddr.sa_family = 1;
ifr.ifr_hwaddr.sa_data [0] = ...;
ioctl ( fd,SIOCSIFHWADDR,&ifr);

3.IP Adresi Verme
Sıfırdan yaratılan tap arayüzü henüz bir IP, Netmask ve Broadcast adresine sahip değildir. Eğer bu değerleri komut satırından atamadıysak kod ile atamamız gerekir.

Şu satırı dahil ederiz.
#include <sys/ioctl.h>
#include <arpa/inet.h>
#include <net/if.h>
Şöyle yaparız.
struct ifreq ifr;
struct sockaddr_in* addr = (struct sockaddr_in*)&ifr.ifr_addr;
const char * name = "eth0";
int fd = socket(PF_INET, SOCK_DGRAM, IPPROTO_IP);

strncpy(ifr.ifr_name, name, IFNAMSIZ);

ifr.ifr_addr.sa_family = AF_INET;
inet_pton(AF_INET, "10.10.2.59", &addr->sin_addr);
if(ioctl(fd, SIOCSIFADDR, &ifr) < 0)
{
  std::cout << "Failed to set IP: " << strerror(errno) << std::endl;
  return -1;
}

close (fd);
Netmask vermek için yine aynı şekilde adres alanı doldurulur.

ioctl (sock,SIOCSIFNETMASK,&ifr);

Broadcast adresi vermek için
ioctl(sock,SIOCSIFBRDADDR);

yapılır.

4. UP Yapma
Şöyle yaparız.
struct ifreq ifr;

const char * name = "eth0";
int fd = socket(PF_INET, SOCK_DGRAM, IPPROTO_IP);

strncpy(ifr.ifr_name, name, IFNAMSIZ);

if(ioctl(fd, SIOCGIFFLAGS, &ifr) < 0)
{
  std::cout << "Failed to get flags: " << strerror(errno) << std::endl;
  return -2;
}

ifr.ifr_flags |= (IFF_UP | IFF_RUNNING);

if(ioctl(fd, SIOCSIFFLAGS, &ifr) < 0)
{
  std::cout << "Failed to set flags: " << strerror(errno) << std::endl;
  return -3;
}alo

close (fd);

5.Okuma
Tap arayüzünden okuma için şöyle yaparız. Eğer arzu edilirse select () çağrısı da kullanılabilir.
char buffer[1600];
read(fd, buffer, sizeof(buffer));
6 Yazma
write (...) çağrısı kullanılır.

7. Kapatma
Tap arayüzünü kapatmak için şöyle yaparız. Kodla yaratılan ağ arüyüzü geçici olduğu için uygulama sonlanınca arayüz de yok edilir. Yani aslında kapatmasak ta olur ama ben kapatmayı tercih ediyorum.
close(fd);
Windows
Windows'ta TUN/TAP sürücüsü kurmak için OpenVPN kurulumunu yaparken diğer tüm seçenekleri kaldırıp sadece TAP seçeneğini kurmak gerekiyor. Kurulan TAP sürücüsünün "Media Sensing" ayarı etkin geliyor ve üzerinde çarpı işareti var. Bu ayarı devre dışı bırakmak için şöyle yaparız.
  1. Go into device manager
  2. Find your Tap Adapter
  3. Right click
  4. Select "Propterties"
  5. Select "Advanced Media Status"
  6. Set it to "Always Connected"
  7. Click Ok
  8. Restart computer.





SHA-1 - Kullanmayın

Giriş
SHA-1 160 bit (20 byte) hash çıktısı verirSHA-1'in kırılması yakındırBirthday attack ile ortalamada 2^80 denemede kırılıyor. SHA-1 halen sertifikalarda kullanılıyor ancak günleri sayılı.

2017 yılında SHA-1 için ilk collision bulundu. Açıklaması şöyle
Actually SHA-1 has been "officially insecure" for a longer time, since an attack method was published in 2011. The 2017 collisions was just the first known case of actually running the attack. But everybody was already quite convinced that the attack worked, and, indeed, the 2017 collision was produced with the expected computational cost.
Buna rağmen bu algoritmayı veritabanında birincil anahtar (primary key) üretmek için kullananlar var.

SHA-1 Düzeltilebilir mi?
Açıklaması şöyle
SHA-1 is broken. We cannot fix it without modifying result (so compability won't be preserved).
Aslında hardened SHA diye bir şey geliştirilmiş. Açıklaması şöyle
That said, we already fixed it. It's called hardened SHA-1; it is immune to the known and similar collision attacks and it is even backwards compatible with SHA-1, sort of. It detects patterns which will occur in a collision attack and are very rare in random data. Hardened SHA-1 is identical to SHA-1 on almost any input, yet won't be the same and an infinitesimally small portion of inputs we see in collision attacks of the class published.

However though there are no currently known attacks on hardened SHA-1 and it isn't much slower. Nobody has the illusion SHA-1 has competitive security with SHA-2 or SHA-3. Even if you need to truncate to 160 bits, these are probably safer options. If you must have backwards compatibility as a quick fix, Hardened SHA-1 is a great trick but you should make plans to switch to SHA-3
SHA-1 GPU Kullanılarak Kırılabilir
Açıklaması şöyle
By default, Microsoft Office 2016* uses AES-256-CBC with 100000 rounds of SHA1 for password verification using a 16 byte salt. AES256 is currently considered the industry standard by many for symmetric encryption. SHA-1 isn't considered a very secure algorithm for password storage since it's a fast algorithm and can be accelerated massively using GPUs. However, since a 100000 iterations are used, this weakness is significantly mitigated (although it still isn'tanywhere near as good as a dedicated password hashing function like bcrypt/argon2), and if you use a strong password, it shouldn't matter either ways
Expansion and Shrinking
SHA-1 expansion ve shrinking denilen bir işlem yapıyor. Expansion ile 512 bit önce 2560 bit'e genişletiliyor. Shrinking ile bir sonraki işlem için 160 bit muhafaza ediliyor.

Java
MessageDigest yazısına taşıdım.

Apache Commons
DigetUtils.sha1() metodu kullanılabilir.

Linux
Komut satırından şöyle yapılabilir.
sha1sum firefox.tar.gz > sha.txt

14 Haziran 2017 Çarşamba

Modbus

Giriş
Modbus protokolünü hep bir kütüphane aracılığıyla kullandım. Protokol karışık ve kodlaması kolay değil.
PDU
3 çeşit PDU var.
1. ASCII PDU
Serisiletişimde kullanılır.
2. RTU PDU
Seri iletişimde kullanılır. ASCII PDU'dan farklı bir zarf kullanır.
3. TCP PDU
TCP iletişimde kullanılır. RTU PDU TCP ile gönderilemez
Responses
Açıklaması şöyle
Following a request, there are 4 possible outcomes from the slave.
  1. The request is successfully processed by the slave and a valid response is sent.
  2. The request is not received by the slave therefore no response is sent.
  3. The request is received by the slave with a parity, CRC or LRC error. The slave ignores the request and sends no response.
  4. The request is received without an error, but cannot be processed by the slave for another reason. The slave replies with an exception response.
In a normal response, the slave echoes the function code. The first sign of an exception response is that the function code is shown in the echo with its highest bit set. All function codes have 0 for their most significant bit. Therefore, setting this bit to 1 is the signal that the slave cannot process the request.
Negative Ack
4. response tipi için geçerli. Açıklaması şöyle
16 (10 Hex) Return Server NAK Count
The response data field returns the quantity of messages addressed to the remote device for which it returned a Negative Acknowledge (NAK) exception response, since its last restart, clear counters operation, or power–up. Exception responses are described and listed in section 7.
Açıklaması şöyle
So NAK are sent when situation 4 occurs and the counter is incremented accordingly.



10 Haziran 2017 Cumartesi

Konum Hesaplama Formülleri - İki Nokta Arasında En Kısa Mesafeyi Hesaplama

İki enlem arası mesafe
İki enlem arasındaki mesafe yaklaşık 111 km uzunluğundadır.

İki boylam arasındaki mesafe
WGS-84 ekvatorun uzunluğunu 40,075.016686 kilometre olarak sabitlemiş durumda. Ekvatorda iki boylam arasındaki mesafe 40,000 / 360 = yaklaşık 110 km uzunluğunda.

1.  Law of Cosines
Formül şöylee
Distance = acos(SIN(lat1)*SIN(lat2)+COS(lat1)*COS(lat2)*COS(lon2-lon1))*6371
2. Yaklaşık Hesaplama - Haversine Formülü
Yaklaşık hesaplama formülleri daha az hassasiyet sahiptir ancak hata payı göz ardı da edilebilir.
GPS ile bulunan iki nokta arasındaki en kısa mesafeyi hesaplamak için Haversine formülü kullanılabilir. 

Haversine aslında Law of Cosines formülünün özelleştirilmiş hali. 

Bu formül dünyayı küre kabul ettiği için biraz yanılma payı olabilir ancak özellikle çok uzun olmayan mesafelerde yanılma payı göz ardı edilebilecek kadar küçük olabiliyor. Hata payı %0.5 kadar olabilir

Bu formülde iki nokta arasındaki Great Circle (Büyük Daire) mesafesi bulunuyor. Great Circle iki nokta arasındaki en kısa mesafe için takip edilen çizgiye verilen isim. Aşağıdaki great circle yay uzunluğunu göstere örneği buradan aldım.



Bu formülde ana hedef iki nokta arasındaki açıyı hesaplamak. Açıklaması şöyle. R dünyanın yarıçapı, theta ise iki nokta arasındaki açı.
İki nokta arasındaki açı hesaplanabilirse dairenin özelliğinden dolayı R*theta ifadesi ile mesafeyi de hesaplayabiliriz.
Kilometre cinsinden formül şöyle.
public static double distFrom(double lat1, double lng1, double lat2, double lng2){
    double earthRadius = 6371.0;//kilometer
    double dLat = Math.toRadians(lat2-lat1);
    double dLng = Math.toRadians(lng2-lng1);
    double sindLat = Math.sin(dLat / 2);
    double sindLng = Math.sin(dLng / 2);
    double a = Math.pow(sindLat, 2) + Math.pow(sindLng, 2)
            * Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2));
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
    double dist = earthRadius * c;

    return dist;
}
Metre cinsinden formül şöyle.
double distance(double fromLat, double fromLon, double toLat, double toLon) {
  double radius = 6378137;   // approximate Earth radius, *in meters*
  double deltaLat = toLat - fromLat;
  double deltaLon = toLon - fromLon;
  double angle = 2 * Math.asin( Math.sqrt(
        Math.pow(Math.sin(deltaLat/2), 2) + 
        Math.cos(fromLat) * Math.cos(toLat) * 
        Math.pow(Math.sin(deltaLon/2), 2) ) );
  return radius * angle;
}
Dünyanın yarıçapını 6371.0 kilometre kabul ediyor. Metre cinsinden hesaplamak için 6371,000 metre, mil cinsinden hesaplamak için 3958.75 mil kabul etmemiz gerekirdi. Formülü Spherical Law of Cosines ile açıklayan bir yazı burada.

Sanırım android.location.Location sınıfı bu formülü kullanıyor. 

2. Tam Olarak Hesaplama - Vincenty's Formülü
Daha yüksek hassasiyetle hesaplama için Geographical Distance sayfasında bahsedilen Vincenty's Formula kullanılabilir.